MAPS: approximate publish/subscribe functionality in peer-to-peer networks

ABSTRACT

Information filtering has been a research issue for years. In an information filtering scenario users information needs are expressed by user subscriptions, and users are notified about published documents or events that match these interests. The combination of the publish/subscribe scenario with the peer-to-peer (P2P) approach of autonomous peers makes high demands on the scalability and the efficiency of such a given highly distributed network. However, in many cases a subscriber is not interested in all the events that match his profile, but rather in a small representative set. In this paper, we present our approach of an approximate publish/subscribe system, that relaxes the assumption for receiving notifications from every information producer in the network. Our work builds upon distributed hash table technology to create and maintain a distributed global directory that contains information about peers' publishing behavior and combines the current peer state and the prediction of the future publishing behavior of a peer to store a subscription only to the most promising peers in the network. Our experimental evaluation shows that approximate information filtering results satisfying recall level and is able to accommodate changes in peer publishing behaviour.

References

1. I. Aekaterinidis and P. Triantafillou. Internet scale string attribute publish/subscribe data networks. In CIKM, 2005.
2. M. Bender, S. Michel, P. Triantafillou, G. Weikum, and C. Zimmer. Improving collection selection with overlap-awareness. In SIGIR, 2005.
3. M. Bender, S. Michel, P. Triantafillou, G. Weikum, and C. Zimmer. P2p content search: Give the web back to the people. In IPTPS), 2006.
4. M. Bender, S. Michel, G. Weikum, and C. Zimmer. The minerva project: Database selection in the context of p2p search. In BTW, 2005.
5. J. Callan. Distributed information retrieval., 2000.
6. A. Carzaniga, D. S. Rosenblum, and A. L. Wolf. Design and evaluation of a wide-area event notification service. TOCS, 2001.
7. C. Chatfield. The Analysis of Time Series - An Introduction. CRC Press, 2004.
8. G. M. D. Corso, A. Gulli, and F. Romani. Ranking a stream of news. In WWW, 2005.
9. J.-P. Dittrich, P. M. Fischer, and D. Kossmann. Agile: Adaptive indexing for context-aware information filters. In SIGMOD, 2005.
10. N. Fuhr. A decision-theoretic approach to database selection in networked ir. TOCS, 1999.
11. L. Gravano, H. Garcia-Molina, and A. Tomasic. Gloss: Text-source discovery over the internet. TODS, 1999.
12. H. Nottelmann and N. Fuhr. Evaluating different methods of estimating retrieval quality for resource selection. In SIGIR, 2003.
13. S. Ratnasamy, P. Francis, M. Handley, R. M. Karp, and S. Shenker. A scalable content-addressable network. In SIGCOMM, 2001.
14. A. I. T. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware, 2001.
15. A. I. T. Rowstron, A.-M. Kermarrec, M. Castro, and P. Druschel. Scribe: The design of a large-scale event notification infrastructure. In NGC, 2001.
16. L. Si, R. Jin, J. P. Callan, and P. Ogilvie. A language modeling framework for resource selection and results merging. In CIKM, 2002.
17. I. Stoica, R. Morris, D. R. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, 2001.
18. C. Tang and Z. Xu. pfilter: Global information filtering and dissemination using structured overlay networks. In FTDCS, 2003.
19. C. Tryfonopoulos, S. Idreos, and M. Koubarakis. Publish/subscribe functionality in ir environments using structured overlay networks. In SIGIR, 2005.
20. C. Tryfonopoulos, M. Koubarakis, and Y. Drougas. Filtering algorithms for information retrieval models with named attributes and proximity operators. In SIGIR, 2004.
21. J. Xu and W. B. Croft. Cluster-based language models for distributed retrieval. In SIGIR, 1999.
22. B. Yang and G. Jeh. Retroactive answering of search queries. In WWW, 2006.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Organizing principles for web applications