BLOOM FİLTRELERİ : ÇEŞİTLERİ VE ANALİZİ

Öz

Bloom filtrelerini ve çe itlerini inceleyen bir çalı manın özetidir. Bloom filtresi sorgulama üyeliklerini desteklemek amacıyla setleri temsil eden rasgele bir veri yapısıdır. 1970’lerde daha çok veri tabanı optimizasyonlarında kullanılmı tır. Bu yakınlarda bilgisayar a ları ile ilgili çalı ma yapanlar daha sık kullanmaya ba lamı tır. Bu çalı mada filtrelerin çe itleri analiz edilecektir

Anahtar Kelimeler

• Bloom Filtreleri, veri yapıları

BLOOM’S FILTERS : THEIR TYPES AND ANALYSIS

Öz

In this paper we discuss Bloom filter in its original form and the varieties of its extensions. A Bloom filter is a randomized data-structure for concisely representing a set in order to support approximate membership queries. Although it was devised in 1970 for the purpose of spell checking, it was seldom used except in database optimization. In recent years, it has been rediscovered by the networking community, and has become a key component in many networking systems applications. In this paper, we will examine and analyse the different types of this filter.

Anahtar Kelimeler

• Bloom Filter, Data Structure

Kaynakça

1. BLOOM, B. (1970). Space/time tradeoffs in hash coding with allowable errors. Communications of the ACM, 13(7).
2. BRODERY, A. & MITZENMACHERZ, M. (2002). Network applications of Bloom Filters : a survey. Proceedings of 40th Annual Allerton Conference. Also available at
3. BYERS, J., CONSIDINE, J., MITZENMACHER, M., & ROST, S. (2002). Informed content delivery across adaptive overly networks. Proceedings of ACM SIGCOMM 2002, pp. 47-60.
4. CARTER, L., & WEGMAN, M. (1979). Universal classes of hash functions. Journal of Computer and System Sciences, pp. 143-154. CS223 Final Project Report.
5. CHANG, F., FENG, W. & LI, K. (2004). Approximate caches for packet classification NSF Grant EIA-0130344, IEEE INFOCOM 2004.
6. CZERWINSKI, S., ZHAO, B.Y., HODES, T., JOSEPH, A.D., & KATZ, R. (1999). An architecture for a secure service discovery service. Proceedings of MobiCom- 99, pp. 24-35.
7. DHARMAPURIKAR, S., KRISHNAMURTHY, P., & TAYLOR, D. (2003). Longest prefix matching using Bloom Filters. Proceedings of the ACM SIGCOMM, pp. 201-212.
8. FAN, L., P. CAO, J. ALMEIDA, & BRODER, A. Z. (2000). Summary cache : a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3), pp. 281-293.

9. FELDMANN, A., & MUTHUKRISHNAN, S. (2000). Tradeoffs for packet classification, IEEE INFOCOM, 2000.
10. FENG, W., KANDLUR, D., SAHA D., SHIN, K., BLUE (1999). A new class of active queue management algorithms, U. Michigan CSE-TR-387-99.
11. FENG, W. & KANDLUR, D.D. (2001). Stochastic fair blue : a queue management algorithm for enforcing fairness. Proceedings of IEEE INFOCOM 2001.
12. HSIAO, P. & HUANG, J. (2001). Geographical region summary service for wireless routing. MobiHoc 2001, Long Beach, CA, USA, pp. 263-266. Also available at CS223 Final Project Report. final.pdf> as
13. HSIAO, P (2001). Geographical region summary service for geographical routing. Mobile Computing and Communications Review, 5(4), pp. 25-39.
14. IAMNITCHI, A., RIPEANU, M. & FOSTER, I. (2002). Locating data in (Small- World?) peer-to-peer scientific collaborations. 1st International Workshop on Peer-to-Peer http://arxiv.org/abs/cs/0209031. IPTPS 2002. Also available at
15. KOLONIARI, G. & PITOURA, E. (2003). Bloom-based filters for hierarchical data. 5th Workshop on Distributed Data Structures and Algorithms (WDAS’03).
16. (2004). Filters for XML-based service discovery in pervasive computing. The Computer Journal, 47(4). Oxford University Press for the BCS.
17. KUMAR, A. & LI, L. (2003). Space-code Bloom Filter for efficient traffic flow measurement. IMC’03 2003, Miami Beach, Florida, USA. Also available at: http://www.imconf.net/imc-2003/papers/p312-kumar1.pdf.
18. LI, J. & JANNOTTI, J. & DE COUTO, D & KARGER, D. & MORRIS, R. (2000). A scalable location service for geographic ad-hoc routing. Proceedings of MobiCom 2000, pp. 120-130.
19. MARAIS, H. & BHARAT, K. (1997). Supporting cooperative and personal surfing with a desktop assistant. In ACM Symposium on User Interface Software and Technology, pp. 129-138
20. MITZENMACHER, M. (2001). Compressed Bloom Filters. Proceedings of the 20th ACM SIGACT Symposium on Principles of Distributed Computing (PODC 2001).
21. (2001). Compressed bloom filters. Proceedings of the 20th ACM SIGACT- SIGOPS Symposium on Principles of Distributed Computing, pp. 144-150.
22. MULLIN, J.K. (1983). A Second look at Bloom Filters. Communications of the ACM, 26(8).
23. (1990). Optimal semijoins for distributed database systems. IEEE Transactions on Software Engineering, 16(5).
24. Passive measurement and analysis project, National Laboratory for Applied Network Research (NLANR). Available at http://pma.nlanr.net/Traces/Traces/
25. REYNOLDS, P. AND VAHDAT, A. (2003). Efficient Peer-to-peer keyword searching. Middleware 2003, Rio de Janeiro Brazil, pp. 21-40. Also available at http://issg.cs.duke.edu/search/.
26. RIVEST, R. (1991). THE MD5 Message-Digest Algorithm. RFC1321.
27. ROUSSKOV, A & WESSELS, D (1998). Cache digests. Computer Networks and ISDN Systems, 30(22-23), pp. 2155-2168.
28. SANCHEZ, L., MILLIKEN,W., SNOEREN, A.,TCHAKOUNTIO, F., JONES, C.,KENT, S.,PARTRIDGE,C., & STRAYER, W. (2001). Hardware support for a hash-based IP traceback. Proceedings of the 2nd DARPA Information Survivability Conference and Exposition.
29. SNOEREN, A. C., PARTRIDGE, L. A. SANCHEZ, C. E. JONES, F. TCHAKOUNTIO, S. T. KENT, & STRAYER, W. T. (2001). Hash-Based IP traceback. Proceedings of the ACM SIGCOMM 2001 Conference (SIGCOMM- 01), volume 31:4 of Computer Communication Review, pp. 3-14.