Abstract
Consider the problem of maintaining a family F of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given \(S,S'\in F\), report every member of \(S\cap S'\) in any order. We show that in the word RAM model, where w is the word size, given a cap d on the maximum size of any set, we can support set intersection queries in \(O(\frac{d}{w/\log ^2 w})\) expected time, and updates in O(1) expected time. Using this algorithm we can list all t triangles of a graph \(G=(V,E)\) in \(O(m+\frac{m\alpha }{w/\log ^2 w} +t)\) expected time, where \(m=|E|\) and \(\alpha \) is the arboricity of G. This improves a 30-year old triangle enumeration algorithm of Chiba and Nishizeki running in \(O(m \alpha )\) time.
We provide an incremental data structure on F that supports intersection witness queries, where we only need to find one \(e\in S\cap S'\). Both queries and insertions take \(O\left( {\sqrt{\frac{N}{w/\log ^2 w}}}\right) \) expected time, where \(N=\sum _{S\in F} |S|\). Finally, we provide time/space tradeoffs for the fully dynamic set intersection reporting problem. Using M words of space, each update costs \(O(\sqrt{M \log N})\) expected time, each reporting query costs \(O(\frac{N\sqrt{\log N}}{\sqrt{M}}\sqrt{op+1})\) expected time where op is the size of the output, and each witness query costs \(O(\frac{N\sqrt{\log N}}{\sqrt{M}} + \log N)\) expected time.
A more detailed version of this paper appears in [1]. Supported by NSF grants CCF-1217338 and CNS-1318294 and a grant from the US-Israel Binational Science Foundation. This research was performed in part at the Center for Massive Data Algorithmics (MADALGO) at Aarhus University, which is supported by the Danish National Research Foundation grant DNRF84.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kopelowitz, T., Pettie, S., Porat, E.: Dynamic set intersection (2014). CoRR abs/1407.6755v2
Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18–31 (1980)
Myers, G.: A Four Russians algorithm for regular expression pattern matching. J. ACM 39(2), 432–448 (1992)
Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39(5), 2075–2089 (2010)
Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time. ACM Transactions on Algorithms 8(4), 34 (2012)
Chan, T.M.: All-pairs shortest paths with real weights in \(o(n^3/\log n)\) time. Algorithmica 50(2), 236–243 (2008)
Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four soviets walk the dog - with an application to Alt’s conjecture. In: Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1399–1413 (2014)
Baran, I., Demaine, E.D., Pǎtraşcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584–596 (2008)
Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. In: Proceedings 55th IEEE Symposium on Foundations of Computer Science (FOCS) (2014). Full manuscript available as arXiv:1404.0799
Chan, T.M.: The art of shaving logs. In: Dehne, F., Solis-Oba, R., Sack, J.-R. (eds.) WADS 2013. LNCS, vol. 8037, p. 231. Springer, Heidelberg (2013)
Pǎtraşcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings 42nd ACM Symposium on Theory of Computing (STOC), pp. 603–610 (2010)
Kopelowitz, T., Pettie, S., Porat, E.: 3sum hardness in (dynamic) data structures (2014). CoRR abs/1407.6756
Demaine, E.D., López-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 743–752 (2000)
Barbay, J., Kenyon, C.: Adaptive intersection and t-threshold problems. In: Proceedings 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 390–399 (2002)
Baeza-Yates, R.: A fast set intersection algorithm for sorted sequences. In: Sahinalp, S.C., Muthukrishnan, S., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol. 3109, pp. 400–408. Springer, Heidelberg (2004)
Bille, P., Pagh, A., Pagh, R.: Fast evaluation of union-intersection expressions. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 739–750. Springer, Heidelberg (2007)
Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40–42), 3795–3800 (2010)
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413–423 (1978)
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)
Björklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 223–234. Springer, Heidelberg (2014)
Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput. 136(1), 25–51 (1997)
Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424–436 (1993)
Brodnik, A., Miltersen, P.B., Munro, J.I.: Trans-dichotomous algorithms without multiplication—some upper and lower bounds. In: Rau-Chaplin, A., Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol. 1272, pp. 426–439. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Kopelowitz, T., Pettie, S., Porat, E. (2015). Dynamic Set Intersection. In: Dehne, F., Sack, JR., Stege, U. (eds) Algorithms and Data Structures. WADS 2015. Lecture Notes in Computer Science(), vol 9214. Springer, Cham. https://doi.org/10.1007/978-3-319-21840-3_39
Download citation
DOI: https://doi.org/10.1007/978-3-319-21840-3_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21839-7
Online ISBN: 978-3-319-21840-3
eBook Packages: Computer ScienceComputer Science (R0)