Abstract
We study the straggler identification problem, in which an algorithm must determine the identities of the remaining members of a set after it has had a large number of insertion and deletion operations performed on it, and now has relatively few remaining members.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13, 422–426 (1970)
Bollobás, B.: Random Graphs. Academic Press, New York (1985)
Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., Varghese, G.: An improved construction for counting Bloom filters. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 684–695. Springer, Heidelberg (2006)
Bose, P., Guo, H., Kranakis, E., Maheshwari, A., Morin, P., Morrison, J., Smid, M., Tang, Y.: On the false-positive rate of Bloom filters. Report, School of Comp. Sci. Carleton Univ. (2007), http://cg.scs.carleton.ca/~morin/publications/ds/bloom-submitted.pdf
Broder, A., Mitzenmacher, M.: Network applications of Bloom filters: A survey. Internet Mathematics 1(4), 485–509 (2005)
Capetanakis, J.I.: Tree algorithms for packet broadcast channels. IEEE Trans. Inf. Theory IT-25(5), 505–515 (1979)
Colbourn, Dinitz, Stinson: Applications of combinatorial designs to communications, cryptography, and networking. In: Walker (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 187, Cambridge University Press, Cambridge (1999)
Cormode, G., Muthukrishnan, S.: What’s hot and what’s not: tracking most frequent items dynamically. ACM Trans. Database Syst. 30(1), 249–278 (2005)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer, Heidelberg (1992)
DeBonis, A., Gasieniec, L., Vaccaro, U.: Generalized framework for selectors with applications in optimal group testing. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 81–96. Springer, Heidelberg (2003)
Du, D.-Z., Hwang, F.K.: Combinatorial Group Testing and Its Applications, 2nd edn. World Scientific, Singapore (2000)
Du, D.-Z., Hwang, F.K.: Pooling Designs and Nonadaptive Group Testing. World Scientific, Singapore (2006)
Eppstein, D., Goodrich, M.T., Hirschberg, D.S.: Improved combinatorial group testing for real-world problem sizes. In: Dehne, F., López-Ortiz, A., Sack, J.-R. (eds.) WADS 2005. LNCS, vol. 3608, Springer, Heidelberg (2005)
Fan, L., Cao, P., Almeida, J., Broder, A.Z.: Summary cache: a scalable wide-area web cache sharing protocol. IEEE/ACM Trans. Networking 8(3), 281–293 (2000)
Farach, M., Kannan, S., Knill, E., Muthukrishnan, S.: Group testing problems with sequences in experimental molecular biology. In: SEQUENCES, p. 357. IEEE Press, New York (1997)
Ganguly, S., Majumder, A.: Deterministic k-set structure. In: Proc. 25th ACM SIGMOD Symp. Principles of Database Systems, pp. 280–289 (2006)
Georgiadis, L., Papantoni-Kazakos, P.: A collision resolution protocol for random access channels with energy detectors. IEEE Trans. on Communications COM-30(11), 2413–2420 (1982)
Goodrich, M.T., Hirschberg, D.S.: Efficient parallel algorithms for dead sensor diagnosis and multiple access channels. In: SPAA. 18th ACM Symp. on Parallelism in Algorithms and Architectures, pp. 118–127. ACM Press, New York (2006)
Greenberg, A.G., Ladner, R.E.: Estimating the multiplicities of conflicts in multiple access channels. In: FOCS 1983. Proc. 24th Annual Symp. on Foundations of Computer Science, pp. 383–392. IEEE Computer Society Press, Los Alamitos (1983)
Greenberg, A.G., Winograd, S.: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32(3), 589–596 (1985)
Hofri, M.: Stack algorithms for collision-detecting channels and their analysis: A limited survey. In: Balakrishnan, A.V., Thoma, M. (eds.) Proc. Inf. Sem. Modelling and Performance Evaluation Methodology, Lecture Notes in Control and Info. Sci., vol. 60, pp. 71–85 (1984)
Hwang, F.K., Sós, V.T.: Non-adaptive hypergeometric group testing. Studia Scient. Math. Hungarica 22, 257–263 (1987)
Minsky, Y., Trachtenberg, A., Zippel, R.: Set reconciliation with nearly optimal communication complexity. IEEE Trans. Information Theory 49(9), 2213–2218 (2003)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Pippenger, N.: Bounds on the performance of protocols for a multiple-access broadcast channel. IEEE Trans. on Information Theory IT-27(2), 145–151 (1981)
Ruszinkó, M., Vanroose, P.: A code construction approaching capacity 1 for random access with multiplicity feedback. Report, Fakultät für Mathematik der Universität Bielefeld, Report no. 94-025 (1994), http://www.math.uni-bielefeld.de/sfb343/preprints/abstracts/apr94025.ps.gz
Shoup, V.: A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic. In: Proc. Int. Symp. Symbolic and Algebraic Computation, pp. 14–21. ACM Press, New York (1991)
Tsybakov, B.S.: Resolution of a conflict of known multiplicity. Problems of Information Transmission 16(2), 134–144 (1980)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Eppstein, D., Goodrich, M.T. (2007). Space-Efficient Straggler Identification in Round-Trip Data Streams Via Newton’s Identities and Invertible Bloom Filters. In: Dehne, F., Sack, JR., Zeh, N. (eds) Algorithms and Data Structures. WADS 2007. Lecture Notes in Computer Science, vol 4619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73951-7_55
Download citation
DOI: https://doi.org/10.1007/978-3-540-73951-7_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73948-7
Online ISBN: 978-3-540-73951-7
eBook Packages: Computer ScienceComputer Science (R0)