{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:41Z","timestamp":1725497261864},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_64","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"739-750","source":"Crossref","is-referenced-by-count":12,"title":["Fast Evaluation of Union-Intersection Expressions"],"prefix":"10.1007","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anna","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"9","key":"64_CR1","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.S.: The input\/output complexity of sorting and related problems. Comm. ACM\u00a031(9), 1116\u20131127 (1988)","journal-title":"Comm. ACM"},{"key":"64_CR2","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. Information and Computation\u00a0136, 25\u201351 (1997)","journal-title":"Information and Computation"},{"key":"64_CR3","doi-asserted-by":"crossref","unstructured":"Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? In: Proceedings of the 27th annual ACM symposium on Theory of computing (STOC 1995), pp. 427\u2013436 (1995)","DOI":"10.1145\/225058.225173"},{"issue":"4","key":"64_CR4","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z. Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. System Sci.\u00a068(4), 702\u2013732 (2004)","journal-title":"J. Comput. System Sci."},{"key":"64_CR5","unstructured":"Barbay, J., Kenyon, C.: Adaptive intersection and t-threshold problems. In: Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02002), pp. 390\u2013399 (2002)"},{"key":"64_CR6","unstructured":"Bille, P., Pagh, A., Pagh, R.: Fast evaluation of union-intersection expressions. Technical Report arXiv:0708.3259v1 (2007), \n                    \n                      http:\/\/arxiv.org"},{"issue":"7","key":"64_CR7","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"B.H. Bloom","year":"1970","unstructured":"Bloom, B.H.: Space\/time trade-offs in hash coding with allowable errors. Communications of the ACM\u00a013(7), 422\u2013426 (1970)","journal-title":"Communications of the ACM"},{"key":"64_CR8","first-page":"636","volume-title":"Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing","author":"A.Z. Broder","year":"2002","unstructured":"Broder, A.Z., Mitzenmacher, M.: Network applications of Bloom filters: A survey. In: Proceedings of the 40th Annual Allerton Conference on Communication, Control, and Computing, pp. 636\u2013646. ACM Press, New York (2002)"},{"issue":"5","key":"64_CR9","doi-asserted-by":"publisher","first-page":"1627","DOI":"10.1137\/S0097539795294165","volume":"28","author":"A. Brodnik","year":"1999","unstructured":"Brodnik, A., Munro, J.I.: Membership in constant time and almost-minimum space. SIAM J. Comput.\u00a028(5), 1627\u20131640 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"64_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"J.L. Carter","year":"1979","unstructured":"Carter, J.L., Wegman, M.N.: Universal classes of hash functions. J. Comput. System Sci.\u00a018(2), 143\u2013154 (1979)","journal-title":"J. Comput. System Sci."},{"key":"64_CR11","first-page":"59","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u00a01978)","author":"L. Carter","year":"1978","unstructured":"Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u00a01978), pp. 59\u201365. ACM Press, New York (1978)"},{"key":"64_CR12","first-page":"107","volume-title":"IEEE Conference on Computational Complexity","author":"A. Chakrabarti","year":"2003","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: IEEE Conference on Computational Complexity, pp. 107\u2013117. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"64_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/11523468_15","volume-title":"Automata, Languages and Programming","author":"E. Chiniforooshan","year":"2005","unstructured":"Chiniforooshan, E., Farzan, A., Mirzazadeh, M.: Worst case optimal union-intersection expression evaluation. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 179\u2013190. Springer, Heidelberg (2005)"},{"key":"64_CR14","unstructured":"Demaine, E.D., L\u00f3pez-Ortiz, A., Munro, J.I.: Adaptive set intersections, unions, and differences. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02000), pp. 743\u2013752 (2000)"},{"issue":"1","key":"64_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"F.K. Hwang","year":"1972","unstructured":"Hwang, F.K., Lin, S.: A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput.\u00a01(1), 31\u201339 (1972)","journal-title":"SIAM J. Comput."},{"key":"64_CR16","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"64_CR17","unstructured":"Mirzazadeh, M.: Adaptive comparison-based algorithms for evaluating set queries. Master\u2019s thesis, University of Waterloo (2004)"},{"key":"64_CR18","first-page":"823","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02005)","author":"A. Pagh","year":"2005","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal Bloom filter replacement. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02005), pp. 823\u2013829. ACM Press, New York (2005)"},{"key":"64_CR19","first-page":"496","volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02000)","author":"M. Thorup","year":"2000","unstructured":"Thorup, M.: Even strongly universal hashing is pretty fast. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u00a02000), pp. 496\u2013497. ACM Press, New York (2000)"},{"key":"64_CR20","first-page":"209","volume-title":"Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC\u00a01979)","author":"A.C. Yao","year":"1979","unstructured":"Yao, A.C.: Some complexity questions related to distributive computing (preliminary report). In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC\u00a01979), pp. 209\u2013213. ACM Press, New York (1979)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:01:24Z","timestamp":1619521284000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_64","relation":{},"subject":[]}}