WORKSHOP REPORT

7th Workshop on Large-Scale Distributed Systemsfor Information Retrieval (LSDS-IR’09)
Claudio Lucchese
C.N.R. – I.S.T.I.
Pisa, Italy
claudio.lucchese@isti.cnr.it

Gleb Skobeltsyn
Google Inc.
Zurich, Switzerland
glebs@google.com

Wai Gen Yee
Dept. of Computer Science
Illinois Institute of Technology
Chicago, IL 60616 USA
yee@iit.edu

Abstract
Due to the dramatically increasing amount of available data,
effective and scalable solutions for data organization andsearch are essential. Distributed solutions naturally provide
promising alternatives to standard centralized approaches.
With the computational power of thousands or millions ofcomputers in clusters or peer-to-peer systems, the challenges
that arise are manifold, ranging from efficient resource
discovery to issues in load balancing and distributed query
processing.
The 2009 edition of the Workshop on Large-Scale Distributed
Systems for Information Retrieval (LSDS-IR'09) provided aforum for researchers to discuss these problems and to define
new directions in research on Distributed Information
Retrieval. The Workshop program featured researchcontributions in the areas of collection selection, similarity
search, index compression, distributed indexing, query
processing, distributed computing, and network formation. In
addition, there were two industry talks on large scale Web
search and distributed computing.

1Introduction

The Web is continuously growing, currently containing more than 20 billion pages (some sourcessuggest more than 100 billion), compared with fewer than 1 billion in 1998. Traditionally, Web-scale
search engines employ large and highly replicated systems, operating on computer clusters in one ormore data centers. Coping with the increasing number of user requests and indexable pages requires
adding more resources. However, data centers cannot grow indefinitely. Scalability problems inInformation Retrieval (IR) have to be addressed in the near future, and new distributed applications
are likely to drive the way in which people use the Web. Distributed IR is the point where these two
directions converge.
The 7th Large-Scale Distributed Systems Workshop (LSDS-IR’09), held on July 23, 2009, andco-located with the 2009 ACM SIGIR Conference in Boston, provided a forum for researchers todiscuss these problems and to define new research directions in the area. It brought together
researchers from the domains of IR and Databases, working on distributed and peer-to-peer (P2P)
ACM SIGIR Forum

34

Vol. 43 No. 2 December 2009

information systems to foster closer collaboration that could have a large impact on the future ofdistributed and P2P IR.
The LSDS-IR’09 Workshop continued the efforts from previous workshops held inconjunction with leading conferences:
••
•
•
•
•

CIKM’08: Workshop on Large-Scale Distributed Systems for Information Retrieval – LSDSIR’08
SIGIR’07: Workshop on Large-Scale Distributed Systems for Information Retrieval – LSDSIR’07
CIKM’06: Workshop on Information Retrieval in Peer-to-Peer Networks – P2PIR’06
CIKM’05: Workshop on Information Retrieval in Peer-to-Peer Networks – P2PIR’05
SIGIR’05: Workshop on Heterogeneous and Distributed Information Retrieval – HDIR’05
SIGIR’04: Workshop on Information Retrieval in Peer-to-Peer Networks – P2PIR’04

In the remainder of this report, we present the Workshop program committee and theprogram. We then summarize the keynote speeches and the presented research papers. We finish
with a discussion of the lessons learned.

2Program Committee

The program committee for the Workshop included:• Karl Aberer, EPFL, Switzerland• Ricardo Baeza-Yates, Yahoo! Research Barcelona, Spain• Gregory Buehrer, Microsoft Live Labs, USA• Roi Blanco, University of A Coruna, Spain• Fabrizio Falchi, ISTI-CNR, Italy• Ophir Frieder, Illinois Institute of Technology, Chicago, USA• Flavio Junqueira, Yahoo! Research Barcelona, Spain• Claudio Lucchese, ISTI-CNR, Italy• Sebastian Michel, EPFL, Switzerland• Wolfgang Nejdl, University of Hannover, Germany• Kjetil Norvag, Norwegian University of Science and Technology, Norway• Salvatore Orlando, University of Venice, Italy• Josiane Xavier Parreira, Max-Planck-Institut Informatik, Germany• Raffaele Perego, ISTI-CNR, Italy• Diego Puppin, Google, USA• Martin Rajman, EPFL, Switzerland• Fabrizio Silvestri, ISTI-CNR, Italy• Gleb Skobeltsyn, EPFL & Google, Switzerland• Torsten Suel, Polytechnic University, USA• Christos Tryfonopoulos, Max-Planck-Institut Informatik, Germany• Wai Gen Yee, Illinois Institute of Technology, USA• Ivana Podnar Zarko, University of Zagreb, Croatia• Pavel Zezula, Masaryk University of Brno, Czech Republic

ACM SIGIR Forum

35

Vol. 43 No. 2 December 2009

3Workshop Program

The Workshop program consisted of two invited keynote talks and nine technical presentations. The
two keynote talks were:
1. Leonidas Kontothanassis (Google Inc.). “The YouTube Video Delivery System.” [1]2. Dennis Fetterly (Microsoft Research). “DryadLINQ: A System for General-Purpose
Distributed Data-Parallel Computing Using a High-Level Language.” [7]Kontothanassis discussed access patterns and trends in video information systems pertaining
to YouTube. Fetterly talked about experiences with using the DryadLINQ system, a programming
environment for writing high performance parallel applications on PC clusters, for Information
Retrieval experiments.
The nine technical talks – in order of presentation – were:
1. Wai Gen Yee, Andrew Yates, Shizhu Liu, and Ophir Frider (Illinois Institute of Technology).
“Are Web User Comments Useful for Search?” [2]2. Andrea Esuli (ISTI-CNR, Italy). “PP-Index: Using Permutation Prefixes for Efficient andScalable Approximate Similarity Search.” [4]3. Sander Bockting (Avanade) and Djoerd Hiemstra (University of Twente). “Collection
Selection with Highly Discriminative Keys.” [5]4. Patrizio Dazzi, Matteo Mordacchini, Raffaele Perego (ISTI-CNR, Italy), Pascal Felber,Lorenzo Leonini (University of Neuchatel), Le Bao Anh, Martin Rajman (EcolePolytechnique Federale de Lausanne, Switzerland), and Etienne Riviere (NTNU, Norway).
“Peer-to-Peer Clustering of Web-browsing Users.” [6]5. Weimao Ke and Javed Mostafa (University of North Carolina). “Strong Ties vs. Weak Ties:
Studying the Clustering Paradox for Decentralized Search.” [8]6. Gabriele Capannini, Fabrizio Silvestri, Ranieri Baraglia, and Franco Maria Nardini (ISTICNR, Italy). “Sorting using BItonic netwoRk wIth CUDA.” [9]7. Linh Thai Nguyen (Orbitz Inc. and Illinois Institute of Technology). “Static Index Pruningfor Information Retrieval Systems: A Posting-Based Approach.” [10]8. Richard McCreadie, Craig Macdonald, and Iadh Ounis (University of Glasgow). “Comparing
Distributed Indexing: To MapReduce or Not?” [11]9. Jimmy Lin (University of Maryland). “The Curse of Zipf and Limits to Parallelization: A
Look at the Stragglers Problem in MapReduce” [12]As in the past years, the Workshop features several papers on P2P-IR. Bockting et al. present
an approach for collection selection based on indexing of popular term combinations. Ke et al. study
the clustering paradox for decentralized search. Finally, Dazzi et al. discuss the clustering of users in
a P2P network for sharing browsing interests.
Another cluster of papers deals with efficiency of large scale infrastructures for information
retrieval. Esuli suggests using permutation prefix indexes for similarity search. Nguyen proposes a
new static index pruning approach. Capannini et al. propose a sorting algorithm that uses CUDA.
McCreadie et al. discuss how suitable the MapReduce paradigm is for efficient indexing. Lin
addresses the load-balancing issue with MapReduce. Finally, on the search quality side, Yee et al.
study the benefits of using user comments for improving search in social Web sites.

ACM SIGIR Forum

36

Vol. 43 No. 2 December 2009

4Presentations

Konthothanassis began the workshop discussing the challenges that YouTube faces, streaming inand out so much data [1]. Already, YouTube is one of the five most popular Web sites with millionsof unique visitors per month [17] and 10 hours of video uploaded per minute [18]. This puts large
strain on their infrastructure, requiring novel techniques for managing physical problems like coolingand power consumption, and software problems, like working sets and security. YouTube continues
to grow, and to maintain quality of service, it maintains a global network of replicated server sites,
which require regular updating to maintain consistency.
Yee et al. continued the discussion on YouTube, illustrating ways of increasing the accuracyof search on content-sharing Web sites [2]. Current practice is to search for videos based on their(publisher-defined) titles, descriptions, and keywords. The problem with this approach is that thisassociated metadata is quite sparse and based on the perspective of a single user. Yee et al. show thatby incorporating the top comment terms into the index processing can improve search accuracy byover 10%. These results are corroborated by similar analyses conducted in [3].
Esuli presented the Permutation Prefix Index (PP-Index), a novel data structure for efficientapproximate similarity search [4], and its application to content-based image retrieval on a collectionof 100M images [19]. The idea is to represent an object by its view of the surrounding world, i.e. alist reference objects sorted by their distance. Objects represented by similar lists are likely to besimilar to each other. Such lists of objects can be stored in a compact prefix tree (about 6 MB forindexing 100M objects), which is used to select a small set of candidate results. The PP-Index
provides good performance in terms of precision and speed, which can be further improved withparallel queries and data replication.
Bockting et al. presented a P2P text search solution called Sophos [5]. Sophos is a collection
selection system that leverages highly-discriminative keys [14] in peer indices to construct a broker
index. The broker index contains keys that are good discriminators to select collections (peers).
Additionally, in order to reduce the number of keys transferred to the broker, the authors employ
query-driven indexing [15].
Dazzi et al. outlined the architecture of a P2P information system, identifying the many
design issues [6]. They focus on the clustering of similar users, with the goal of reducing thequerying cost; if similar users are topologically close to each other, then queries, logically, have ashorter distance to travel to find relevant results. The problems with user clustering include designingways to represent collections, designing the right collection similarity metrics, handling unbalanced
loads, and handling malicious peers. Such problems are fundamental to the design of P2P
information systems.
The second part of the workshop devoted to Large-Scale systems started from a keynote byDennis Fetterly. Fetterly talked about DryadLINQ [20] - a system for general-purpose distributed
data-parallel computing using a high-level language. The talk covered architecture of Dryad - aninfrastructure for parallel and distributed programming from Microsoft Research which models
dataflow of the application using DAG, and basics of LINQ (Language INtegrated Query) - a general
purpose language that adds native data querying capabilities to .NET languages. The talk finishedwith several examples of using DryadLINQ in practice and lessons learned. More information about
DeyadLINQ is available at http://research.microsoft.com/projects/dryadlinq.
Ke presented a study on decentralized search in P2P environments [8]. Typically, search issupported by a semantic overlay network, where two peers are linked by a neighborhood relationshipwith high probability if they own similar content. Such probability is controlled by the so called
clustering exponent: a large clustering exponent boosts links among very similar pages, while a small
clustering exponent allows connections between less similar neighbors that speed up the search
ACM SIGIR Forum

37

Vol. 43 No. 2 December 2009

process. Ke showed that for each dataset there exists a best tuning of the clustering exponent thatallows for improved precision and speed in search.
Capannini et al. discussed the possible advantages in using recent “many-core” architectures,and in particular GPUs, for the basic task of sorting [9], which is a building block for many important
problems, such as indexing in IR. Further, Capannini illustrated an efficient implementation of abitonic sorting network for GPUs. The main challenge is to reshape the bitonic sort computationaccording to a stream programming model, which organizes data as streams and expresses allcomputation as kernels. The proposed implementation provides significant speed-ups, especially withlarge amounts of data.
Nguyen showed a way of static index pruning, trying to combine the benefits of both
document-centric and term-centric pruning [10]. The intuition of his work is that document-centricpruning incorrectly allows all documents to stay in a collection and term-centric pruning allows all
terms to stay in an index. The problem is that not all documents and not all terms are equally
popular, so some of each should be removed. Experimental results are impressive for a low pruning
level, outperforming both document- and term-centric pruning. However, as the pruning levelincreases, document-centric pruning outperforms his approach. His work would be improved with abetter cost function so that his approach would work at least as well as the better of document-centric
and term-centric pruning.
McCreadie et al. discussed efficient ways to implement distributed indexing of a large-scale
textual collection [11]. They implemented and compared three approaches: 1) baseline indexing with
map-reduce as outlined in [16], 2) distributed indexing without map-reduce, and 3) an optimized
indexing algorithm based on map-reduce. The map phase of the optimized algorithm does more local
processing of the input and uses compression to emit less intermediate data which positively affects
performance. The authors performed extensive experiments demonstrating that the proposed
optimized indexing with map-reduce scales well and achieves a noticeable speed up while indexing alarge corpus of 25M documents on 19 machines.
Lin showed one of the limiting factors of Map Reduce – that it can only run as quickly as theslowest process [12]. His claim is that, in practice, data sets cannot be partitioned evenly. This isdemonstrated by works such as [13], who showed that a power law distribution exists in many realworld phenemona. Workload processing times will reflect these skewed data set sizes by skewed
computation times. Future work includes new ways of partitioning workload for better loadbalancing.

5Final Remarks

The presented work represents a cross-section of today’s distributed and P2P information search andprocessing problems. Large-scale, distributed systems [1, 2] with sparse descriptions require a greatamount of resources to allow speedy and accurate search. Other techniques that can improve theefficiency or speed of distributed data search are novel indexing techniques based on approximations,selective keys and specialized topologies [4, 5, 6, 8]. Modern approaches to solving the problems ofhandling large scale distributed data include the use of map-reduce-like technologies [7, 11]. Suchapproaches are not without peril, however, as partitioned workloads will tend to have skewed sizes[12].
We plan for the next edition of the Large Scale Distributed Systems for Information Retrieval
Workshop to be held next year in the ACM SIGIR Conference. At that conference, we expect to see
greater development on the handling of large data sets by data partitioning and distribution. For more
information on this year’s Workshop, please see http://lsdsir09.isti.cnr.it/.

ACM SIGIR Forum

38

Vol. 43 No. 2 December 2009

6References

1. L. Kontothanassis. “The YouTube Video Delivery System.” In Proc. LSDS-IR, 2009, p. 7.
CEUR Workshop Proceedings, Vol. 80, ISSN 1613-0073.
2. W. G. Yee, A. Yates, S. Liu, and O. Frider. “Are Web User Comments Useful for Search?” InProc. LSDS-IR, 2009, pp. 63-70. CEUR Workshop Proceedings, Vol. 80, ISSN 1613-0073.
3. M.
Potthast,“Measuring
theDescriptivenessofWebComments.”
http://www.webis.de/research/projects/opinioncloud. Accessed September, 2009.
4. A. Esuli. “PP-Index: Using Permutation Prefixes for Efficient and Scalable Approximate
Similarity Search.” In Proc. LSDS-IR, 2009, pp. 17-24. CEUR Workshop Proceedings, Vol. 80,
ISSN 1613-0073.
5. S. Bockting and D. Hiemstra. “Collection Selection with Highly Discriminative Keys.” In Proc.
LSDS-IR, 2009, pp. 9-16. CEUR Workshop Proceedings, Vol. 80, ISSN 1613-0073.
6. P. Dazzi, M. Mordacchini, R. Perego, P. Felber, L. Leonini, M. Rajman, and E. Riviere “Peer-toPeer Clustering of Web-browsing Users.” In Proc. LSDS-IR, 2009, pp. 71-78. CEUR Workshop
Proceedings, Vol. 80, ISSN 1613-0073.
7. D. Fetterly. “DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing
Using a High-Level Language.” In Proc. LSDS-IR, 2009, p. 8. CEUR Workshop Proceedings,Vol. 80, ISSN 1613-0073.
8. W. Ke, J. Mostafa. “Strong Ties vs. Weak Ties: Studying the Clustering Paradox forDecentralized Search.” In Proc. LSDS-IR, 2009, pp. 49-56. CEUR Workshop Proceedings, Vol.
80, ISSN 1613-0073.
9. G. Capannini, F. Silvestri, R. Baraglia, F. M. Nardini. “Sorting using BItonic netwoRk wIthCUDA.” In Proc. LSDS-IR, 2009, pp. 33-40. CEUR Workshop Proceedings, Vol. 80, ISSN
1613-0073.
10. L. T. Nguyen. “Static Index Pruning for Information Retrieval Systems: A Posting-BasedApproach.” In Proc. LSDS-IR, 2009, pp. 25-32. CEUR Workshop Proceedings, Vol. 80, ISSN
1613-0073.
11. R. McCreadie, C. Mcdonald, I. Ounis. “Comparing Distributed Indexing: To MapReduce orNot?” In Proc. LSDS-IR, 2009, pp. 41-48. CEUR Workshop Proceedings, Vol. 80, ISSN 16130073.
12. J. Lin. “The Curse of Zipf and Limits to Parallelization: A Look at the Stragglers Problem in
MapReduce” In Proc. LSDS-IR, 2009, pp. 57-62. CEUR Workshop Proceedings, Vol. 80, ISSN
1613-0073.
13. G. K. Zipf. “Human Behavior and the Principle of Least-Effort.” Addison-Wesley, 1949.
14. I. Podnar, M. Rajman, T. Luu, F. Klemm, and K. Aberer. “Scalable Peer-to-Peer Web Retrieval
with Highly Discriminative Keys.” In Proc. IEEE 23rd International Conference on DataEngineering (ICDE 2007), IEEE Computer Society Press, pp. 1096-1105, 2007.
15. G. Skobeltsyn, T. Luu, I. Podnar Zarko, M. Rajman, and K. Aberer. “Web Text Retrieval with a
P2P Query-Driven Index.” In Proc. 30th Annual International ACM SIGIR Conference,Amsterdam, The Netherlands, 2007.
16. J. Dean and S. Ghemawat. “MapReduce: Simplified Data Processing on Large Clusters.” In Proc.
of OSDI, 2004.
17. comScore. U.S. Online Video Viewing Surges 13 Percent in Record-Setting December. Press
Release. Feb. 4, 2009. http://comscore.com/index.php/Press_Events/Press_Releases/2009/2/
US_Online_Video_Viewing_Sets_Record.
18. YouTube Fact Sheet. Accessed September, 2009. http://www.youtube.com/t/fact_sheet

ACM SIGIR Forum

39

Vol. 43 No. 2 December 2009

19. P. Bolettieri, A. Esuli, F. Falchi, C. Lucchese, R. Perego, and F. Rabitti. “Enabling Content-Based
Image Retrieval in Very Large Digital Libraries”. In Proc. of the 2nd Workshop on Very Large
Digital Libraries, 2 October 2009, Corfu, Greece.
20. Y. Yu, M. Isard, D. Fetterly, M. Budiu, U. Erlingsson, P. Kumar Gunda and J. Currey.
“DryadLINQ: A System for General-Purpose Distributed Data-Parallel Computing Using a HighLevel Language”. In Proceedings of OSDI, 2008.

ACM SIGIR Forum40

Vol. 43 No. 2 December 2009