TL;DR
This paper tackles the challenge of efficiently crawling the vast and growing Web of Linked Data by proposing a machine learning approach to predict whether a discovered URI will lead to RDF data. By learning from features of the URI itself and its context, their method significantly improves the accuracy of identifying relevant data sources, reducing wasted effort compared to traditional heuristic methods.
What Problem Does This Paper Address?
The Web of Linked Data, where data is interconnected using RDF (Resource Description Framework), is expanding rapidly. To effectively harvest this data, specialized crawlers are needed. A core challenge for these crawlers is deciding which Uniform Resource Identifiers (URIs) are worth downloading. Simply downloading every URI is infeasible due to the sheer volume of data and network costs. Traditional crawlers often rely on heuristics, like checking file extensions or HTTP Content-Type headers, to filter out non-RDF URIs. However, these heuristics are imperfect; they can miss RDF data embedded in seemingly non-RDF documents (e.g., RDFa in HTML) or incorrectly flag RDF data as non-RDF. This leads to a trade-off between crawling coverage and efficiency. This paper aims to bridge this gap by developing a more intelligent URI selection mechanism that can accurately predict RDF relevance, thereby improving both coverage and efficiency.
Methods
The authors propose a machine learning-based approach to predict the RDF relevance of a "hard URI" – one whose relevance isn't immediately obvious from its extension or header. They extract two main types of features:
- Intrinsic URI Features: These are derived directly from the URI's components (scheme, authority, host, path, query, fragment).
- Extrinsic URI Features: These require interacting with the URI or its context:
- URI Header Features: Obtained via an HTTP HEAD request (e.g., Content-Type).
- URI Representation Features: Derived from the content of the referring URI's RDF graph, including direct properties and sibling URIs.
They define several atomic feature sets (e.g., F+t for target URI intrinsic and header features, F+r for referring URI intrinsic features) and explore combinations of these.
For the prediction task, they employ an online learning approach using the FTRL-Proximal (Follow-the-Regularized-Leader-Proximal) algorithm. This is crucial because the Web of Linked Data is dynamic, and the crawler needs to adapt its predictions as it encounters new data. FTRL-Proximal is chosen for its effectiveness in large-scale, sequential learning problems, balancing accuracy and sparsity. They also introduce a subsampling strategy to handle the rarity of positive (RDF-relevant) examples and the cost of downloading to verify relevance.
Datasets
The paper describes experiments conducted on a dataset of approximately 103K URIs from 9,825 different hosts, generated by a Breadth-First Search (BFS) crawl. The authors do not explicitly mention releasing a new benchmark dataset but rather use data collected from a BFS crawl for their experiments.
Key Insights and Ideas
- Heuristics are Insufficient: The paper strongly suggests that relying solely on file extensions and Content-Type headers misses a significant amount of valuable RDF data, highlighting the need for more sophisticated methods.
- Context Matters: Features derived not just from the target URI but also from its referring URI and its neighbors (siblings, direct properties) in the RDF graph are crucial for accurate prediction.
- Online Learning is Key: The dynamic nature of the Linked Data Web necessitates an online learning approach that can adapt predictions as new data is encountered, making FTRL-Proximal a suitable choice.
- Target URI Features are Important: While context is vital, features directly from the target URI itself (
F+t) are shown to be essential for good performance.
Key Results
The empirical evaluation revealed several key findings:
- Best Feature Combination: The combination of intrinsic and header features of the target URI, along with intrinsic features of the referring URI and direct properties (
F+t+r+p), achieved the best performance, yielding an F-measure of 0.8216 and an accuracy of 0.7902 when evaluated with offline classifiers (SVM, KNN, Naive Bayes). - Sibling Features' Impact: Augmenting the best feature set with sibling URI features (
F+t+r+p+x) did not significantly improve performance, suggesting that sibling information might be redundant or less impactful than other features in this context. - LDCOC Performance: The proposed crawler, LDCOC (Linked Data Crawler with Online Classifier), which uses the FTRL-Proximal algorithm and the
F+t+r+pfeature set, outperformed baseline crawlers (including BFS and crawlers with offline classifiers) in terms of the percentage of retrieved RDF-relevant URIs after crawling 300K URIs. This demonstrates the practical benefit of their online learning approach.
Limitations and Future Work
- Subsampling Strategy: While a subsampling strategy is employed to manage the cost of obtaining true labels, it introduces a bias. The authors acknowledge this by assigning importance weights to subsampled examples.
- Generalization: The paper suggests that the method can be generalized to crawl other kinds of Linked Data formats like JSON-LD and Microdata, which would be a natural direction for future work.
- Feature Engineering: While they explored various feature sets, further research into more sophisticated feature engineering or representation learning could potentially yield even better results.
- Scalability of Offline Classifiers: The paper notes that crawlers with offline classifiers pre-trained on small datasets do not perform as well in a dynamic environment, implying that continuous retraining or more robust online methods are superior.
Summary updated