{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:39Z","timestamp":1760202699181,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_39","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"470-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Dynamic Set Intersection"],"prefix":"10.1007","author":[{"given":"Tsvi","family":"Kopelowitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"39_CR1","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Dynamic set intersection (2014). CoRR abs\/1407.6755v2"},{"issue":"1","key":"39_CR2","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"WJ Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.: A faster algorithm computing string edit distances. J. Comput. Syst. Sci. 20(1), 18\u201331 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"39_CR3","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1145\/128749.128755","volume":"39","author":"G Myers","year":"1992","unstructured":"Myers, G.: A Four Russians algorithm for regular expression pattern matching. J. ACM 39(2), 432\u2013448 (1992)","journal-title":"J. ACM"},{"issue":"5","key":"39_CR4","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput. 39(5), 2075\u20132089 (2010)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"39_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/2344422.2344424","volume":"8","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in $$o(mn)$$ time. ACM Transactions on Algorithms 8(4), 34 (2012)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"39_CR6","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in $$o(n^3\/\\log n)$$ time. Algorithmica 50(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Buchin, K., Buchin, M., Meulemans, W., Mulzer, W.: Four soviets walk the dog - with an application to Alt\u2019s conjecture. In: Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1399\u20131413 (2014)","DOI":"10.1137\/1.9781611973402.103"},{"issue":"4","key":"39_CR8","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., P\u01cetra\u015fcu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, 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","DOI":"10.1109\/FOCS.2014.72"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-40104-6_20","volume-title":"Algorithms and Data Structures","author":"TM Chan","year":"2013","unstructured":"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)"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings 42nd ACM Symposium on Theory of Computing (STOC), pp. 603\u2013610 (2010)","DOI":"10.1145\/1806689.1806772"},{"key":"39_CR12","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: 3sum hardness in (dynamic) data structures (2014). CoRR abs\/1407.6756"},{"key":"39_CR13","unstructured":"Demaine, E.D., L\u00f3pez-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\u2013752 (2000)"},{"key":"39_CR14","unstructured":"Barbay, J., Kenyon, C.: Adaptive intersection and t-threshold problems. In: Proceedings 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 390\u2013399 (2002)"},{"key":"39_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-540-27801-6_30","volume-title":"Combinatorial Pattern Matching","author":"R Baeza-Yates","year":"2004","unstructured":"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\u2013408. Springer, Heidelberg (2004)"},{"key":"39_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/978-3-540-77120-3_64","volume-title":"Algorithms and Computation","author":"P Bille","year":"2007","unstructured":"Bille, P., Pagh, A., Pagh, R.: Fast evaluation of union-intersection expressions. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 739\u2013750. Springer, Heidelberg (2007)"},{"issue":"40\u201342","key":"39_CR17","doi-asserted-by":"publisher","first-page":"3795","DOI":"10.1016\/j.tcs.2010.06.002","volume":"411","author":"H Cohen","year":"2010","unstructured":"Cohen, H., Porat, E.: Fast set intersection and two-patterns matching. Theor. Comput. Sci. 411(40\u201342), 3795\u20133800 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"39_CR18","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput. 7(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"39_CR19","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"39_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/978-3-662-43948-7_19","volume-title":"Automata, Languages, and Programming","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, 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\u2013234. Springer, Heidelberg (2014)"},{"issue":"1","key":"39_CR21","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1006\/inco.1997.2632","volume":"136","author":"S Albers","year":"1997","unstructured":"Albers, S., Hagerup, T.: Improved parallel integer sorting without concurrent writing. Inf. Comput. 136(1), 25\u201351 (1997)","journal-title":"Inf. Comput."},{"issue":"3","key":"39_CR22","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-63307-3_80","volume-title":"Algorithms and Data Structures","author":"A Brodnik","year":"1997","unstructured":"Brodnik, A., Miltersen, P.B., Munro, J.I.: Trans-dichotomous algorithms without multiplication\u2014some upper and lower bounds. In: Rau-Chaplin, A., Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 1997. LNCS, vol. 1272, pp. 426\u2013439. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T05:47:45Z","timestamp":1676958465000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}