This work investigates the use of focussed crawling techniques for the discovery of environmental multimedia Web resources that provide air quality measurements and forecasts. Focussed crawlers automatically navigate the hyperlinked structure of the Web and select the hyperlinks to follow by estimating their relevance to a given topic, based on evidence obtained from the already downloaded pages. Given that air quality measurements and particularly air quality forecasts are presented not only in textual form, but are most commonly encoded as multimedia, mainly in the form of heatmaps, we propose the combination of textual and visual evidence for predicting the bene t of fetching an unvisited Web resource. First, text classi cation is applied to select the relevant hyperlinks based on their anchor text, a surrounding text window, and URL terms. Further hyperlinks are selected by combining their text classi cation score with an image classi cation score that indicates the presence of heatmaps in their source page. A pilot evaluation indicates that the combination of textual and visual evidence results in improvements in the crawling precision over the use of textual features alone.
H.3 [Information Systems]: Information Storage and Retrieval
Environmental conditions, such as the weather, air quality, and pollen concentration, are considered as one of the factors with a strong impact on the quality of life, since they directly a ect human health (e.g., allergies and asthma), a variety of human outdoor activities (ranging from agriculture to sports and travel planning), as well as major environmental issues (such as the greenhouse e ect). In order to support both scientists in forecasting environmental phenomena and also people in everyday action planning, there is a need for services that provide access to information related to environmental conditions that is gathered from several sources, with a view to obtaining reliable data. Monitoring stations established by environmental organisations and agencies typically perform such measurements and make them available, most commonly, through Web resources, such as pages, sites, and portals. Assembling and integrating information from several such providers is a major challenge, which requires, as a rst step, the automatic discovery of Web resources that contain environmental measurement data; this can be cast as a domain{speci c search problem.
Domain{speci c search is mainly addressed by techniques
that fall into two categories: (i) the domain{speci c query
submission to a general{purpose search engine followed by
post{retrieval ltering, and (ii) focussed crawling. Past
research in the environmental domain (e.g., [
Focussed (or topical ) crawlers exploit the graph structure
of the Web for the discovery of resources about a given topic.
Starting from one or more seed URLs on the topic, they
download the Web pages addressed by them and mine their
content so as to extract the hyperlinks contained therein and
select the ones that would lead them to pages relevant to the
topic. This process is iteratively repeated until a su cient
number of pages is fetched (i.e., downloaded). To predict
the bene t of fetching an unvisited Web resource is a
major challenge since crawlers need to estimate its relevance to
the topic at hand based solely on evidence obtained from
the already downloaded pages. To this end, state{of{the{
art approaches (see [
This work investigates focussed crawling for the
automatic discovery of environmental Web resources, in
particular those providing air quality measurements and
forecasts; see Figure 1 for some characteristic examples. Such
resources report the concentration values of several air
pollutants, such as sulphur dioxide (SO2), nitrogen oxides and
dioxide (NO+NO2), thoracic particles (PM10), ne
particles (PM2.5) and ozone (O3), measured or forecact for
speci c regions [
This motivates us to form the hypothesis that the presence of a heatmap in a page already estimated to be an air quality resource indicates that it is indeed highly relevant to the topic. Therefore, if such a page has already been downloaded by a crawler focussed on air quality, it would be a useful source of global evidence for the selections to be subsequently performed by such a focussed crawler. To this end, this work proposes a classi er{guided focussed crawling approach that estimates the relevance of a hyperlink to an unvisited Web resource based on the combination of (i) textual evidence from its local context and (ii) global visual evidence indicating the presence of a heatmap in its parent page. This is achieved by the late fusion of text and image classi cation con dence scores obtained by supervised machine learning methods based on Support Vector Machines (SVMs).
The main contribution of this work is a novel focussed
crawling approach that takes into account multimedia
(textual + visual) evidence for predicting the bene t of fetching
an unvisited Web resource based on the combination of text
and image classi ers. State{of{the{art classi er{guided
focussed crawlers rely mainly on textual evidence [
The remainder of this paper is structured as follows. Section 2 discusses related work. Section 3 presents the proposed focussed crawling approach, Section 4 describes the evaluation setup, and Section 5 reports and analyses the experimental results. Section 6 concludes this work and outlines future research directions. 2.
Focussed crawling techniques have been researched since
the early days of the Web [
Previous research has de ned local context in textual terms
as the lexical content that appears around a given hyperlink
in its parent page. It may correspond to the anchor text of
the hyperlink, a text window surrounding it, the words
appearing in its URL, and combinations thereof. Virtually all
focussed crawlers [
Earlier focussed crawlers (e.g., [
Focussed crawling has not really been previously explored
in the environmental domain. The discovery of
environmental Web resources has previously been addressed mainly
through the submission of domain{speci c queries to general{
purpose search engines, followed by the application of a
post{retrieval classi cation step for improving precision [
This work proposes a classi er{guided focussed crawling approach for the discovery of environmental Web resources providing air quality measurements and forecasts. To this end, it estimates the relevance of a hyperlink to an unvisited resource based on the combination of its local context with global evidence associated with its parent page. Local context refers to the textual content appearing in the vicinity of the hyperlink in the parent page. Motivated by the frequent occurrence of heatmaps in such Web resources, we consider the presence of a heatmap in a parent page as global evidence for its high relevance to the topic.
An overview of the proposed focussed crawling approach is depicted in Figure 3. First the seed pages are added to the list of URLs to fetch. In each iteration, a URL is picked from the list and the page corresponding to this URL is fetched (i.e., downloaded) and parsed to extract its hyperlinks. In the simple case that the focussed crawler estimates the relevance of a hyperlink pointing to an unvisited page p based only on its local context, the decision to fetch p depends solely on the output of an appropriately trained text classi er. Therefore, a page is fetched if the con dence score s of the text{based classi er is above an experimentally set threshold t1.
However, there are cases in which the local context is not su cient to e ectively represent relevant hyperlinks, leading them to obtain low con dence scores below the set threshold t1, and thus to not being fetched by the focussed crawler. In this case, global evidence can be used for adjusting the estimate for the hyperlink's relevance. This is motivated by the `topical locality' phenomenon of Web pages linking to other pages that are similar in content; therefore, if there is strong evidence of the parent's page relevance, then the relevance estimates of its children pages should be adjusted accordingly.
As mentioned before, the presence of heatmaps in a Web resource already assumed to be an air quality resource is a strong indication that it is indeed highly relevant to the topic. Therefore, we propose the consideration of heatmap presence in the parent page as global evidence to be used for adjusting the relevance estimate of hyperlinks with textbased con dence scores below the required threshold t1 (in practice, a lower bound threshold t2 is also set; this threshold is also experimentally tuned). In particular, the estimate of relevance of each hyperlink is adjusted to correspond to the late fusion of a text and a heatmap classier: score = f (text classif ier; heatmap classif ier), and the page is fetched if its score t1. In our case, a binary heatmap classi er is considered and the fusion function f is set to correspond to max. This results in a page being fetched if either its text-based con dence score is above t1 or if its text-based con dence score is above t2 (t2 < t1) and its parent page contains at least one heatmap. Next, the text and heatmap classi ers employed in this work are described. 3.1
Text{based link classi cation is performed using a
supervised machine learning approach based on SVMs and a
variety of textual features extracted from the hyperlink's local
context. SVMs are applied due to their demonstrated e
ectiveness in similar applications [
Each hyperlink is represented using textual features extracted from the following elds: a: anchor text of the hyperlink, h: the terms extracted from the URL of the hyperlink; string sequences are split in punctuation marks and common URL extensions (e.g., com) and pre xes (e.g., www) are removed; s: the terms extracted from a text window of 50 characters surrounding the hyperlink; this text window does not contain the anchor text of adjacent links (i.e., the window stops as soon as it encounters another link), so: the terms extracted from a text window of 50 characters surrounding the hyperlink when overlap to the adjacent links is allowed.
Combinations of the above lead to the following ve representations corresponding to concatenations of the respective elds: a+s, a+so, a+h, a+h+s, and a+h+so.
In the training phase, a list of positive and negative samples are collected rst, so as to build a vocabulary for representing the samples in the textual feature space and also for training the model. Each sample corresponds to a hyperlink pointing to a Web page on air quality measurements and forecasts and its associated a+so representation. The vocabulary is built by accumulating all the terms from the a+so representations of the samples and eliminating all stopwords. This representation was selected so as to lead to a richer feature space, compared to the sparser a, s, and a+s representations, while also remaining relatively noise free compared to the a+h+s and a+h+so representations which are likely to contain more noise given the di culties in successfully parsing URLs.
Each sample is represented in the textual feature space
spanned by the created vocabulary using a tf:idf = tf (t; d)
n
log( df(t) ) weighting scheme, where tf (t; d) is the frequency
of term t in sample d and idf (t) is the inverse document
frequency of term t in the collection of n samples, where
df (t) is the number of samples containing that term.
Furthermore, a feature representing the number of geographical
terms in the sample's a+so representation is added, given
the importance of such terms in the environmental domain
[
In the testing phase, each sample is represented as a feature vector based on the tf:idf of the terms extracted from one of the proposed representation schemes (a, a+s, a+so, a+h, a+h+s, or a+h+so) and the number of geographical terms within the same representation. The text{based classi cation score of each hyperlink is then obatined by the employing the classi er on the feature vector and corresponds to a con dence value that re ects the distance of the testing sample to the hyperplane.
Our model was trained using 711 samples (100 positive, 611 negative). Each sample corresponds to a hyperlink pointing to page providing air quality measurements and forecasts; these hyperlinks were extracted from 26 pages about air quality obtained from ODP and previous empirical studies conducted by domain experts in the context of the project PESCaDO2. It should be noted that both the hyperlinks and their parent pages are di erent from the seed set used in the evaluation of the focussed crawler (see Section 4). The generated lexicon consists of 207 terms with the following being the 10 most frequent in the training corpus: days, ozone, air, data, quality, today, forecast, yesterday, raw, and current. The geographical lexicon consists of 3,625 terms obtained from a geographical database. 3.2
Heatmap recognition is performed by applying a recently
developed approach by our research group [
In particular, the following three extracted MPEG{7 features that capture color and texture aspects of human perception were the most e ective:
Scalable Color Descriptor (SC): a Haar{transform based encoding scheme that measures color distribution over an entire image, quantized uniformly to 256 bins, Edge Histogram Descriptor (EH): a scale invariant visual texture descriptor that captures the spatial distribution of edges; it involves division of image into 16 non{overlapping blocks and edge information calculated for each block in ve edge categories, and Homogenous Texture Descriptor (HT): describing directionality, coarseness, and regularity of patterns in images based on a lter bank approach that employs scale and orientation sensitive lters.
Their early fusion (SC{EH{HT), as well as the feature EH on its own produced the best results when employing an SVM classi er with an RBF kernel. The evaluation was performed by training the classi er on a dataset of 2,200 images (600 relevant, i.e., heatmaps) and testing it on dataset of 2,860 images (1,170 heatmaps)4.
In this work, both the EH and the SC{EH{HT models trained on the rst dataset are employed. An image is classi ed as a heatmap if at least one of these classi ers considers it to be a heatmap, i.e., a late fusion approach based on a logical OR is applied. 2Personalised Environmental Service Con guration and Delivery Orchestration (http://www.pescado-project.eu/). 3Adaptive Hierarchical Density Histogram. 4Both datasets are available at: http://mklab.iti.gr/ project/heatmaps.
A pilot study is performed for evaluating the performance of the proposed focussed crawling approach.
A set of 10 seeds5 (listed in Table 1) was selected, similarly to before, i.e., using ODP and the outcomes of empirical studies conducted by domain experts in the context of the project PESCaDO. Half of them contain at least one heatmap. Starting from these 10 seeds, a crawl at depth 1 is performed. A total of 807 hyperlinks are extracted from these 10 seeds and several focussed crawling approaches are applied for deciding which ones to fetch. These are evaluated in the following two sets of experiments. 4.1
Experiment 1: This experiment examines the relative merits of the di erent text{based representations of hyperlinks (i.e., a, a+s, a+so, a+h, a+h+s, and a+h+so). In this case, a text{based classi er{guided focussed crawling is applied for each representation and a page is fetched if its text{based con dence score is above a threshold t1. Experiments are performed for t1 values ranging from 0:0 to 0:9 at step 0:1. When t1 = 0:0, the crawl corresponds to a breadth{ rst search where all hyperlinks are fetched and no focussed crawling is performed.
Experiment 2: This experiment investigates the e ectiveness of incorporating multimedia evidence in the form of heatmaps in the crawling process. In this case, a page pointed by a hyperlink is fetched if the hyperlink's text{ based con dence score is above t1 or if its text{based con dence score is above t2 (t2 < t1) and its parent page contains at least one heatmap. The text{based con dence scores are obtained from the best performing classi er in Experiment 1. Experiments are performed for t1 and t2 values ranging from 0:0 to 0:9 at step 0:1, while maintaining t2 < t1. These experimental results are compared against two baselines: (i) the results of the corresponding text{based focussed crawler for threshold t1, and (ii) the results of the corresponding text{based focussed crawler for threshold t2.
To determine the presence of a heatmap in the parent page of a hyperlink, the page is parsed (since it is already downloaded) and the hyperlinks pointing to images are compiled into a list. The crawler iteratively downloads each image in the list, extracts its visual features, and applies the heatmap classi cation until a heatmap is recognised or a maximum number of images is downloaded from each page (set to 20 in our experiments).
In both experiments, when a hyperlink appears more than once within a seed page, only the one with the highest score is taken into consideration for evaluation purposes. 5These URLs are di erent to the ones used when training the classi ers.
The standard retrieval evaluation metrics of precision and
recall are typically applied for assessing the e ectiveness of
a focussed crawler. Precision corresponds to the proportion
of fetched pages that are relevant and recall to the
proportion of all relevant pages that are fetched. The latter
requires knowledge of all relevant pages on a given topic, an
impossible task in the context of the Web. To address this
limitation, two recall{oriented evaluation techniques have
been proposed [
All 807 extracted hyperlinks were manually assessed. After applying some light URL normalisation (e.g., deleting trailing slashes) and removing duplicates, 689 unique URLs remain. These correspond both to internal (within{site) and to external links that were assessed using the following three{point relevance scale: (highly) relevant : Web resources that provide air quality measurements and forecasts. These data should either be visible on the page or should appear after selecting a particular value from options (e.g., region, pollutant, time of day, etc.) provided from drop{down menus. partially relevant : Web resources that are about air quality measurements and forecasts, but do not provide actual data. Examples include Web resources that list monitoring sites and the pollutants being measured, explain what such measurements mean, describe methods, approaches, and research for measuring, validating, and forecasting air quality data, or provide links to components, systems, and applications that measure air quality. non{relevant : Web resources that are not relevant to air quality measurements and forecasts, including resources that are about air quality and pollution in general, discussing, for instance, its causes and e ects. Overall, our crawled dataset contains 232 (33.7%) highly relevant pages, 51 (7.4%) partially relevant, and 406 (58.9%) non{relevant ones. n o i isce .03 r p
A closer inspection revealed that 162 (69.8%) of the highly relevant pages were all crawled from seed no. 2 in Table 1 (http://airnow.gov/). These correspond to internal links pointing to pages with air quality measurements/forecasts, each regarding a di erent U.S. region. This, in conjunction with the fact that all these links obtained really high scores (over 0:9) by our text classi er led us to remove them from further consideration as they would signi cantly skew the evaluation results. Therefore, the evaluation was performed only for the pages crawled from the nine remaining seeds and these are the results reported in Section 56. Starting from the 9 seeds, our crawled dataset contains 526 URLs: 70 (13.3%) highly relevant pages, 50 (9.5%) partially relevant, and 406 (77.2%) non{relevant ones.
To apply the performance metrics presented above, these multiple grade relevance assessments are mapped into binary relevance judgements in two di erent ways, depending on whether we are strictly interested in discovering resources containing air quality data, or whether we would also be interested in information about air quality measurements and forecasts. In particular, two mappings are considered: strict : when considering only highly relevant Web resources as relevant and the rest (partially relevant and non{relevant) as non{relevant, and 6It should be noted that http://airnow.gov/ appears in the list of our crawled pages even when removed from the seed list, since it is linked from other seed pages. However, since crawling is performed at depth 1, its own outlinks are not considered any further. lenient : when considering both highly relevant and partially relevant Web resources as relevant.
The distributions of relevance assessments in these two cases are listed in Table 2.
Our implementation is based on Apache Nutch (http://
nutch.apache.org/), a highly extensible and scalable open
source Web crawler software project. To convert it to a
focussed crawler, its parser was modi ed so as to lter the links
being fetched based on our proposed approach. The text{
based classi er was implemented using the libraries of the
Weka machine learning software (http://www.cs.waikato.
ac.nz/ml/weka/), while the implementation of the visual
classi er was based on the LIBSVM [
Experiment 1: The results of this rst experiment that evaluates the e ectiveness of the di erent textual represen0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 Text{based baseline a+s
(fetch if s >= t2) tations employed by the text{based focussed crawler are depicted in Figures 4 and 5, when applying strict and lenient relevance assessments, respectively.
The a+s classi er{guided focussed crawler achieves the highest overall precision, both for the strict and the lenient cases, and for t1 = 0:4, indicating the bene ts of combining the anchor text with the terms obtained from a non{ overlapping text window. It also achieves the highest accuracy, which is equal to that of the a+h and a+h+s classiers; these two classi ers have though slightly lower precision compared to that of a+s. This indicates that the URL is potentially a useful source of evidence and that application of more advanced techniques for extracting terms from an URL is probably required for reaching its full potential. The a+so and a+h+so classi ers are the least e ective for lower t1 values indicating that the additional terms present in the overlapping text window introduce noise that leads to the misclassi cation of non{relevant hyperlinks. Furthermore, all focussed crawlers improve upon precision for t1 = 0:0 that corresponds to general{purpose crawling. As expected, the absolute values of precision are much higher in the lenient case, compared to the strict.
Experiment 2: The second experiment aims to allow us to gain insights into the feasibility and potential bene ts of incorporating multimedia in the form of heatmaps in the crawling process. To this end, it combines a+s, the best performing text{based classi er from the rst experiment, with results from the heatmap classi er. First, the results of the heatmap classi cation are presented.
Each of the nine seeds contains 15 images on average as identi ed by our parser. On average, 8 images are downloaded from each seed before a heatmap is found or the image list ends. Out of the 75 downloaded images, 74 were correctly classi ed, with 3 being heatmaps. This means that 8 of the 9 seeds were classi ed accurately for the presence of heatmaps in them (all apart from seed no. 10 in Table 1). This is probably due to the di culty in parsing the speci c Web resource and also in recognising its images as heatmaps, as they correspond to non{typical heatmaps, di erent to the ones in our training set. On average, 10 seconds were required per Web resource for the downloading, feature extraction, and classi cation of its images; however, this overhead could be reduced by applying parallelisation.
Tables 3 and 4 present the results of the second experiment, when applying strict and lenient relevance assessments, respectively, for t1 and t2 values ranging from 0:0 to 0:9 at step 0:1, while maintaining t2 < t1. The results are compared against the two baselines listed in the tables' last column and last row respectively. The values in bold correspond to improvements over both baselines.
The observed substantial improvements for multiple threshold values provide an indication of the bene ts of incorporating visual evidence as global evidence in a focussed crawler. Consider the best performing classi er when strict relevance assessments are employed: it achieves precision of 0:44 for t1 = 0:9 and t2 = 0:3, while the text{based focussed crawler for the same t1 = 0:9 achieves precision 0:30. An examination of the results shows that the improvements are due to the fact that 65% of the newly added hyperlinks, i.e., those with text{based classi cation score between 0:3 and 0:9, are relevant.
This work proposed a novel classi er{guided focussed crawling approach for the discovery of environmental Web resources providing air quality measurements and forecasts that combines multimedia (textual + visual) evidence for predicting the bene t of fetching an unvisited Web resource. The results of our pilot study provide a rst indication of the e ectiveness of incorporating visual evidence in the focussed crawling process over the use of textual features alone.
Large{scale experiments are currently planned for fully
assessing the potential bene ts of the proposed
multimedia focussed crawling approach, including experiments for
improving the e ectiveness of the textual classi cation by
taking into account also the textual content of the entire
parent page, similar to previous research [
This work was supported by MULTISENSOR (contract no. FP7{610411) and HOMER (contract no. FP7{312388) projects, partially funded by the European Commission.