Bookmark Hierarchies and Collaborative Recommendation

Benjamin Markines, Lubomira Stoilova, Filippo MenczerAAAI 2006

Abstract: Traditional web recommendation systems often rely on text analysis or the global hyperlink graph. This paper introduces GiveALink, a system that utilizes the latent semantic information within personal bookmark hierarchies. By transforming individual browser folder structures into a collective intelligence engine, GiveALink generates a similarity-based recommendation framework. Empirical results demonstrate that this approach achieves recommendation precision comparable to major search engines, even with a significantly smaller index.

Introduction

In the mid-2000s, the landscape of web discovery was dominated by two paradigms: algorithmic search engines and social bookmarking sites using "folksonomies" (flat tags). While effective, these methods often overlooked the rich, structured data inherent in how individuals organize information. Users naturally categorize bookmarks into nested folders, creating personal taxonomies that reflect nuanced semantic relationships. GiveALink was developed to harvest these "human-edited taxonomies" to build a robust, content-agnostic recommendation engine.

Methodology

The GiveALink system processes individual bookmark trees to construct a global similarity graph through several key steps:

  1. Hierarchical Similarity: The system employs Lin’s information-theoretic measure to calculate similarity between URLs based on their relative positions in a user's folder tree. Links sharing a deep, specific folder are considered more similar than those sharing only a high-level root folder.
  2. Collaborative Aggregation: Individual similarity scores are averaged across all users who have bookmarked the same pair of URLs, creating a "global" semantic map.
  3. Prestige and Novelty: The system adapts PageRank for undirected similarity graphs to identify authoritative "Prestige" URLs. Furthermore, it identifies "novel" recommendations by detecting violations of transitivity—suggesting links that are semantically close in the network but have not yet been directly co-located by users.
Figure 1: Illustration of hierarchical bookmark structures for two users, Alice and Bob, showing how shared and unique folders contribute to similarity measures.

Datasets and Implementation

The research utilized data from GiveALink.org, where 996 users donated bookmark files containing over 60,000 unique URLs. Despite the relatively small size of the dataset compared to the scale of the web, the resulting similarity matrix (with a 1.3% density) provided a dense enough network for meaningful recommendation. The authors released an anonymized version of this matrix to the research community to foster further web mining research.

Evaluation and Results

A user study involving 86 subjects and 336 queries was conducted to evaluate the system's performance against Google’s "related" search service. The primary metric used was precision-recall.

Figure 4: Precision-Recall curves comparing GiveALink's similarity-based recommendations (circles) against Google's "related" search results (squares).

The results indicated that GiveALink’s similarity measure performed comparably to Google for top-ranked results (low recall). Crucially, when the evaluation was restricted to URLs indexed by both systems, GiveALink’s hierarchical approach actually outperformed Google’s link-and-text-based algorithms. Another significant finding was that incorporating "Prestige" (popularity) into the recommendation score actually decreased user satisfaction, as participants preferred niche, highly relevant results over generic popular ones.

Insights and Conclusion

The success of GiveALink underscores the value of hierarchical structures over flat tags. Folders capture levels of abstraction that tags miss, providing a finer representation of human knowledge. Because the system is content-agnostic, it effectively recommends non-textual media like PDFs and images.

While the "coverage gap"—the challenge of indexing the vast web via user donations—remains a hurdle, the study proves that "wisdom of the crowd" captured in folder structures can rival the performance of industrial-scale search engines. Future work involves integrating these hierarchical measures with traditional IR techniques and improving the data acquisition process through browser integrations.

Summary updated

BibTeX
@inproceedings{markines2006bookmark,
  author = {Benjamin Markines and Lubomira Stoilova and Filippo Menczer},
  title = {{Bookmark Hierarchies and Collaborative Recommendation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure