215 research outputs found
Retrieval of the most relevant facts from data streams joined with slowly evolving dataset published on the web of data
No full textFinding the most relevant facts among dynamic and hetero- geneous data published on theWeb of Data is getting a growing attention in recent years. RDF Stream Processing (RSP) engines offer a baseline solution to integrate and process streaming data with data distributed on the Web. Unfortunately, the time to access and fetch the distributed data can be so high to put the RSP engine at risk of losing reactiveness, especially when the distributed data is slowly evolving. State of the art work addressed this problem by proposing an architectural solution that keeps a local replica of the distributed data and a baseline maintenance policy to refresh it over time. This doctoral thesis is investigating advance policies that let RSP engines continuously answer top-k queries, which require to join data streams with slowly evolving datasets published on the Web of Data, without violating the reactiveness constrains imposed by the users. In particular, it proposes policies that focus on freshing only the data in the replica that contributes to the correctness of the top-k results
Scaling the monitoring of approximate top-k queries in streaming windows
No full textThe continuous search for the k best results given a query (top-k) in a data stream is a problem that has gained a lot of attention in recent years, especially in social media and IoT contexts. In these contexts it is essential that the system is able to respond reactively. Therefore, in this study we address how to scale the monitoring of approximate continuous top-k queries to guarantee the reactiveness of the system.
In this paper we introduce a scalable distributed version of the MinTopK+N algorithm that allows the system to remain reactive when the load increases. In addition, we present a scale-out/in algorithm that allows the system to add instances to cope with workload increments and remove instances to avoid over-provisioning. Furthermore, in a set of managed experiments, we demonstrated how the increase in the workload could affect the system performance and the impact of the instant of triggering scaling actions on the system performance. Finally, we present a study on the impact of the scaling action on the correctness of the result, showing that the scaling algorithm does not negatively impact the correctness of the results, and in certain conditions, it can even improve the quality of the approximation
Towards a Top-K SPARQL Query Benchmark Generator
No full textThe research on optimization of top-k SPARQL query would largely benefit from the establishment of a benchmark that allows comparing different approaches. For such a benchmark to be meaningful, at least two requirements should hold: 1) the benchmark should resemble reality as much as possible, and 2) it should stress the features of the topk SPARQL queries both from a syntactic and performance perspective. In this paper we propose Top-k DBPSB: an extension of the DBpedia SPARQL benchmark (DBPSB), a benchmark known to resemble reality, with the capabilities required to compare SPARQL engines on top-k queries
Using rank aggregation in continuously answering SPARQL queries on streaming and quasi-static linked data
No full textWeb applications that combine dynamic data stream with distributed background data are getting a growing attention in recent years. Answering in a timely fashion, i.e., reactiveness, is one of the most important performance indicators for those applications. The Semantic Web community showed that RDF Stream Processing (RSP) is an adequate framework to develop this type of applications. However, RSP engines may lose their reactiveness due to the time necessary to access the background data when it is distributed over the Web. State-of-the-art RSP engines remain reactive using a local replica of the background data, but it progressively becomes stale if not updated to reflect the changes in the remote background data. For this reason, recently, the RSP community has investigated maintenance policies of the local replica that guarantee reactiveness while maximizing the freshness of the replica. Previous works simplified the problem with several assumptions. In this paper, we investigate how to remove some of those simplification assumptions. In particular, we target a class of queries for which multiple policies may be used simultaneously and we show that rank aggregation can be effectively used to fairly consider their alternative suggestions. We provide extensive empirical evidence that rank aggregation is key to move a step forward to the practical solution of this problem in the RSP context
When a FILTER Makes the Difference in Continuously Answering SPARQL Queries on Streaming and Quasi-Static Linked Data
No full textWe are witnessing a growing interest for Web applications that (i) require to continuously combine highly dynamic data stream with background data and (ii) have reactivity as key performance indicator. The Semantic Web community showed that RDF Stream Processing (RSP) is an adequate framework to develop this type of applications. However, when the background data is distributed over theWeb, even RSP engines risk losing reactiveness due to the time necessary to access the background data. State-of-the-art RSP engines remain reactive using a local replica of the background data, but such a replica progressively become stale if not updated to reflect the changes in the remote background data. For this reason, recently, the RSP community investigated maintenance policies (collectively named Acqua) that guarantee reactiveness while maximizing the freshness of the replica. Acquaâs policies apply to queries that join a basic graph pattern in a window clause with another basic graph pattern in a service clause. In this paper, we extend the class of queries considered in Acqua adding a FILTER clause that selects mapping in the background data. We propose a new maintenance policy (namely, the Filter Update Policy) and we show how to combine it with Acqua policies. A set of experimental evaluations empirically proves the ability of the proposed policies to guarantee reactiveness while keeping the replica fresher than with the Acqua policies
Critiquing the pursuit of island sustainability
No full textThis article critiques a focus on ‘sustainable development’ which highlights a liveable
‘future’ without paying adequate attention to what, we argue, are more pressing issues
for a liveable present. We contend that, while inherently commendable, the thrust of
many current initiatives related to sustainable development, especially those associated
with climate change, promote an ethos which crowds out other pressing policy pursuits
with more immediate relevance – although often also associated with sustainable
development – such as health, basic education, poverty reduction, and productive
employment and livelihoods. Small Island Developing States (SIDS) are at the forefront
of these initiatives, given their prominence in discussions on sustainable development,
but especially climate change, alongside the basic challenges that they face in
maintaining viable economies. Long-term thinking and planning is needed and
welcomed; but we may now have gone too far in the opposite direction in terms of
aiming for sustainable development in, and for, a distant future that emphasises climate
change, without better balancing of that concern with the pressing needs of the
moment
Phorinia breviata Tachi and Shima 2006
No full textPhorinia breviata Tachi and Shima, 2006 * Phorinia breviata Tachi and Shima, 2006: 260. Type locality: Japan, Fukuoka Pref., Fukuoka City, Mt. Aburayama. Material examined: North Korea, Kangvǒn-do Prov., Kumgang-san Mts., Onjong-ri near Kymgan-san hotel, 28. 08. 1987, 1 male, leg. E. Kierych. Distribution: Palaearctic: Japan (Hokkaido, Honshu, Shikoku, Tsushima Island). Oriental and Oceanian regions (Tachi and Shima 2006). First record from Korea. Remarks: In the first version of this paper I have given the information that among the specimens examined I found male belonging to the Phorinia aurifrons Robineau-Desvoidy, 1830 (after the Key to the insects of Russian Far East. Vol. VI. Diptera and Siphonaptera. Pt 3. Vladivostok. 2004. 124. Fam. Tachinidae. Richter: 197-198). However, one of reviewers, in his comments wrote: ” Phorinia aurifrons Robineau-Desvoidy (…) is considered to be misidentified from East Asia by some authors (see Tachi & Shima 2006, O’Hara et al. 2009, Shima 2014). The author is recommended to confirm identification of this species. If the species P. aurifrons really occurs in North Korea, it is very interesting”. My repeated examination of the specimen from Korea confirmed the suspicions of reviewer. Finally, I decided that it was P. breviata Tachi and Shima.Published as part of DRABER-MOŃKO, Agnieszka, 2015, State of knowledge of the tachinid fauna of Eastern Asia, with new data from North Korea. Part V. Exoristinae, pp. 79-98 in Fragmenta Faunistica 58 (2) on page 90, DOI: 10.3161/00159301FF2015.58.2.079, http://zenodo.org/record/625182
Towards a top-k SPARQL query benchmark generator
No full textLAUREA MAGISTRALELe query top-k query che ritornano i k migliori risultati ordinati secondo
una funzionedefinita dall’utente stanno ottenendo sempre più attenzione
nelle comunità delle basi di dati e del SemanticWeb. L’ordine è una
proprietà importante che può essere sfruttata per accelerare l’elaborazione
delle query, ma, allo stato dell’arte, i motori SPARQL in genere non usano
l’ordine allo scopo di ottimizzarel’elaborazione dellequery: le query top-k
sono per lo più elaborateprima materializzando i risultati e poi ordinandoli
(materialize-then-sort). In questo modo il motore SPARQL prima calcola
tutte le soluzioni corrispondenti (ad esempio migliaia) anche se ne sono
richieste solo un numero k limitato (ad esempio dieci).
Lavori recenti hanno proposto un approccio differente alla valutazione
di query top-k:split-and-interleave. Questo metodo prima divide la funzione
di ordinamento in parti e poi fa in modo di valutarla via via che vengono
trovati i risultati e non solo alla fine.Questo metodo si è dimostrato in
grado di migliorare le prestazioni delle query top- k sia nei database che
nel Semantic Web. Nella letteratura corrente non esiste, però, un lavoro di
valutazione comparativa di motori SPARQL per quel che riguarda le query
top-k. Come spesso accade, la causa principale di questa frammentazione
risiede nella mancanza di un benchmark. Per favorire lo sviluppo della ricerca
sull’ottimizzazione diquery top-k in SPARQL, crediamo che sia giunto
il momento di definire un benchmarkdi querySPARQL top- k.
Un benchmark per essere significativo, dovrebbero avere almeno due requisiti:
1 ) dovrebbe essere simile, per quanto possibile, alla realtà e 2)
dovrebbe insistere sulle caratteristiche che distinguono le query top- k dallequery
SPARQL tradizionali sia dal punto di vista sintattico, vale a dire, le
query devono contenere clausole di ordinamento, sia dal punto di vista delle
prestazioni, ovvero il mix di query dovrebbe stressare i motori SPARQL là
dove sono più deboli nel valutare le query top-k.
In questa tesi ho investigato la seconda condizione, estendendo il DBpedia
SPARQL Benchmark (DBPSB) [Morsey et al., 2011] con le capacità necessarie per confrontare motori SPARQL su query top-k. Il benchmark da
me proposto usa lo stesso insieme di dati, gli stessi indicatori di prestazione,
e gli stessi test driver di DBPSB. La parte innovativa del mio lavoro di tesi
consiste in un algoritmo per creare query top-k a partire dalle query ausiliarie
di DBPSB. Per generare le query top-k il mio algoritmo ha bisogno
di conoscere un insieme di variabili rispetto a cui ordinare (rankable variabile)
i risultati delle query query top-k e di alcune informazioni statistiche
sull’insieme di dati. A questo scopo ho sviluppato un approccio che esplora
la collezione di dati collezionando sia le statistiche che le rankable variabile.
Una volta che l’informazione necessaria a generare le query top-k è disponibile,
per ogni query ausiliaria di DBPSB il mio algoritmo genera in modo
casuale la funzione di ordinamento e aggiunge alla query le clausole ORDER
BY e LIMIT. L’algoritmo assume che: 1) maggiore sia il numero di oggetti
diversi da ordinare, maggiore sia il tempo di esecuzione; 2) maggiori siano il
numero di rankable variable, maggiore sia il tempo di esecuzione; 3) più alta
sia la selettività dei predicati rispetto a cui si ordina, minore sia il tempo
di esecuzione; e 4) la clausola limit sia ininfluente. Ho comparato con il
benchmark proposto quattro motori SPARQL. La valutazione sperimentale
conferma le ipotesi 2) e 4), ma non permette di dare una risposta definitiva
rispetto alle ipotesi 1) e 3).Top-k queries which returning the top k results ordered according to a
user-defined scoring function are gaining more and more attention in the
Database and Semantic Web communities. Order is an important property
that can be exploited to speed up query processing. Also, state-of-theart
SPARQL engines typically do no exploit order for query optimization
purposes: Top-k queries are mostly managed with a materialize-then-sort
processing scheme that computes all the matching solutions (e.g. thousands)
even if only a limited number k (e.g. ten) are requested.
Recent works have shown that an efficient split-and-interleave processing
scheme could be adopted to improve the performance of top-k SPARQL
queries. A consistent comparison of those works does not exist in current
literature. As often occurs, the main cause for this fragmentation resides in
the lack of a SPARQL benchmark covering top-k SPARQL queries. To foster
the work on top-k query processing within the Semantic Web community,
we believe that it is the right time to define a top-k SPARQL benchmark.
For the benchmark to be meaningful, at least two requirements should
hold: 1) the benchmark should resemble reality as much as possible, and 2)
it should stress the features that distinguish top-k queries from traditional
SPARQL queries both from a syntactic perspective, i.e., queries should contain
rank-related clauses, and from a performance perspective, i.e. the query
mix should insist on different characteristics of the queried data, which are
central to top-k query answering, so to stress the evaluated systems in several
running conditions. Recent works on SPARQL query benchmarks help
satisfying the first requirement.
In this thesis, I investigate the second requirement, by extending DBpedia
SPARQL Benchmark (DBPSB) [Morsey et al., 2011] with the capabilities
required to compare SPARQL engines on top-k queries. The Top-k DBpedia
SPARQL Benchmark (Top-k DBPSB) proposed in this thesis uses the same
dataset, performance metrics, and test driver of DBPSB. The innovative
part of my work consists in an algorithm to create the Top-k queries from the Auxiliary queries of the DBPSB and its datasets. To generate top-k
queries, my algorithm needs to have rankable variable that can be used in
the scoring function part of the Top-k queries and some statistical information
about the dataset. To this end, I developed an approach that explores
the dataset collecting meaningful rankable variables and statistics. Once all
the required information is available, it is possible to generate top-k queries
for each DBPSB Auxiliary queries. My algorithm randomly generates the
scoring function and adds ORDERBY and LIMIT clause to complete the
Top-k queries. We have four research hypothesis: 1) the more rankable objects,
the more execution time, 2) the more rankable predicates, the more
execution time, 3) the more selectivity, the less execution time, and 4) the
more the limit value, the same execution time (except ARQ Rank).We run
the Top-K DBPSB against different four SPARQL Engines. The results
of the extensive experimental evaluation confirm hypothesis 2) and 4) but
do not confute the other two assumptions 1) and 3), which require further
research
On relevant query answering over streaming and distributed data
No full textLe applicazioni che combinano (join in inglese) flussi di dati (stream in inglese) con dati distribuiti sul Web stanno riscuotendo crescente attenzione negli ultimi anni. Rispondere in modo tempestivo (cioè essere reattivi) è il più importante degli indicatori di successo per queste applicazioni. La comunità del Semantic Web ha dimostrato che l'RDF Stream Processing (RSP) è adeguato per sviluppare questo tipo di applicazioni, ma anche per un sistema RSP rimanere reattivo può essere difficile quando i dati distribuiti evolvono lentamente. Questo accade perché l'accesso ai dati distribuiti può richiedere molto tempo e la frequenza massima di accesso a tali dati può essere limitata.
Lo stato dell'arte dell’RSP risolve questo problema proponendo un approccio architetturale che mantiene una replica dei dati distribuiti in locale al sistema RSP. La replica locale diventa progressivamente obsoleta se non è aggiornata per riflettere le modifiche fatte ai dati distribuiti. Per questo motivo, recentemente, la comunità degli RSP ha studiato diverse politiche di mantenimento della replica locale che garantiscono la reattività e al contempo massimizzano la freschezza della replica. Le politiche di mantenimento investigate si concentrano su una classe di query che combina dati in uno stream con dati in una sorgente distribuita.
Questa tesi va oltre lo stato dell’arte focalizzandosi su query che cercano in continuo le più importanti combinazioni di dati presenti sia nello stream che nella sorgente distribuita. I contributi di questo studio sono varie politiche di mantenimento della replica locale per due classi di query: i) query che filtrano i dati nella sorgente distribuita prima di combinarli con i dati nello stream e ii) query di tipo top-k in cui la funzione di ordinamento coinvolge dati che appaiono sia nello stream che nella sorgente di dati distribuita.
Il contributo di questa tesi di dottorato sono politiche di mantenimento avanzate che consentono ai sistemi RSP di rispondere in modo reattivo alle due classi di query sopra descritte. Intuitivamente, le politiche proposte riescono là, dove lo stato dell’arte falliva perché aggiornano solo dei dati della replica che contribuiscono all’identificazione dei risultati più importanti.
Per la classe di query che devono filtrare i dati distribuiti, la tesi propone una nuova politica di mantenimento che si focalizza sui dati che più probabilmente supereranno le condizioni del filtro e che, quindi, potrebbero influire sulle valutazioni future. Questa politica funziona per le query in cui il filtro ha selettività elevate, ma altre politiche funzionano meglio quando la selettività è bassa. Per risolvere questo problema, un secondo contributo di questa tesi è un algoritmo che aggrega le opinioni di più politiche.
Per quanto riguarda, invece, la classe delle query top-k, i contributi della tesi sono un nuovo algoritmo top-k che combina flussi di dati e sorgenti di dati distribuite e due politiche di mantenimento della replica locale ottimizzate per query top-k. Le valutazioni sperimentali dimostrano empiricamente la capacità delle politiche proposte di garantire la reattività, fornendo al contempo risultati più accurati e pertinenti rispetto allo stato dell'arte.Web applications that join streaming with distributed data to provide relevant answers are getting a growing attention in recent years. Answering in a timely fashion, i.e., reactively, is one of the most important performance indicators for those applications.
The Semantic Web community showed that RDF Stream Processing (RSP) is an adequate framework to develop this type of applications. However, remaining reactive can be challenging, especially when the distributed data is slowly evolving, because accessing the distributed data can be highly time consuming as well as rate-limited.
State-of-the-art work addresses this problem by proposing an architectural approach that keeps a local replica of the distributed data. The local replica progressively becomes stale if not updated to reflect the changes in the remote distributed data. For this reason, recently, the RSP community investigated maintenance policies of the local replica that guarantee reactiveness while maximizing the freshness of the replica. The investigated maintenance policies focus on a class of queries that join a data stream with a distributed data source.
This thesis goes beyond the state of the art, focusing on finding the most relevant answers by continuously answering query over streaming and distributed data, while considering the reactiveness constraints imposed by the users. The contributions of this study are various maintenance policies, which are tailored for two classes of queries: i) queries that have to filter data in the distributed dataset before joining it with streaming data, and ii) top-k queries where the scoring function involves data that appears both in the streaming and the distributed datasets.
The contributions of this doctoral thesis are advance policies that let RSP engines continuously answer the two classes of queries described above. In particular, the proposed policies focus on refreshing only the data in the replica that contributes to the relevancy of the results.
For the class of queries that have to filter the distributed data, a new maintenance policy is proposed. Intuitively, the Filter Update Policy updates data which is likely to pass the filter condition and may affect the future evaluations. While the Filter Update Policy works for queries where the filter has high selectivities, other policies work better for low selectivity. To solve this problem, as the second contribution, a rank aggregation algorithm introduced to fairly consider the opinions of multiple policies simultaneously.
In the next step, focusing on the class of top-k queries, the contribution is an extended top-k query evaluation which considers the join of streaming data with the distributed dataset. Keeping a local replica of the distributed dataset, two maintenance policies are proposed to approximately answer the continuous top-k query. The experimental evaluations empirically prove the ability of the proposed policies to guarantee reactiveness, while providing more accurate and relevant results than the state of the art.DIPARTIMENTO DI ELETTRONICA, INFORMAZIONE E BIOINGEGNERIAComputer Science and Engineering29CERI, STEFANOBONARINI, ANDRE
An icy layer of isolation: Prince Edward Island’s sea-bound particularity
No full textThe types and degrees of insularity experienced in islands provide considerable material for academics. In the case of Prince Edward Island (PEI), being an Island combined with the isolation caused by sea ice covering the waters around PEI, has impacted Islanders’ sense of relative insularity. Even after the construction of a fixed link to the mainland, Islanders continue to relish in a sense of distinctiveness linked to their Island condition. Since European settlement, PEI’s sea ice barrier has periodically cut off channels of communication and transportation resulting in many societal effects. As ocean temperatures rise due to Climate Change, ice conditions are changing, bringing with them increased coastal erosion and other effects. This article investigates PEI’s relationship with
its frozen sea-bound particularity. Drawing upon the Island’s history, culture, and climate data, as well as from the field of Island Studies, the article asks the question: how has this
‘icy layer of isolation’ affected Islanders’ sense of place over time? And what are the potential implications of the effects of Climate Change for PEI
- …
