Search | arXiv e-print repository

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"/> <meta name="viewport" content="width=device-width, initial-scale=1"/>  <link rel="apple-touch-icon" sizes="180x180" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/apple-touch-icon.png"> <link rel="icon" type="image/png" sizes="32x32" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-32x32.png"> <link rel="icon" type="image/png" sizes="16x16" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon-16x16.png"> <link rel="manifest" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/site.webmanifest"> <link rel="mask-icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/safari-pinned-tab.svg" color="#b31b1b"> <link rel="shortcut icon" href="https://static.arxiv.org/static/base/1.0.0a5/images/icons/favicon.ico"> <meta name="msapplication-TileColor" content="#b31b1b"> <meta name="msapplication-config" content="images/icons/browserconfig.xml"> <meta name="theme-color" content="#b31b1b">  <title>Search | arXiv e-print repository</title> <script defer src="https://static.arxiv.org/static/base/1.0.0a5/fontawesome-free-5.11.2-web/js/all.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/base/1.0.0a5/css/arxivstyle.css" /> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ messageStyle: "none", extensions: ["tex2jax.js"], jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\$","\$"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true, ignoreClass: '.*', processClass: 'mathjax.*' }, TeX: { extensions: ["AMSmath.js", "AMSsymbols.js", "noErrors.js"], noErrors: { inlineDelimiters: ["$","$"], multiLine: false, style: { "font-size": "normal", "border": "" } } }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script src='//static.arxiv.org/MathJax-2.7.3/MathJax.js'></script> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/notification.js"></script> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/bulma-tooltip.min.css" /> <link rel="stylesheet" href="https://static.arxiv.org/static/search/0.5.6/css/search.css" /> <script src="https://code.jquery.com/jquery-3.2.1.slim.min.js" integrity="sha256-k2WSCIexGzOj3Euiig+TlR8gA0EmPjuc79OEeY5L45g=" crossorigin="anonymous"></script> <script src="https://static.arxiv.org/static/search/0.5.6/js/fieldset.js"></script> <style> radio#cf-customfield_11400 { display: none; } </style> </head> <body> <header><a href="#main-container" class="is-sr-only">Skip to main content</a>  <div class="attribution level is-marginless" role="banner"> <div class="level-left"> <a class="level-item" href="https://cornell.edu/"><img src="https://static.arxiv.org/static/base/1.0.0a5/images/cornell-reduced-white-SMALL.svg" alt="Cornell University" width="200" aria-label="logo" /></a> </div> <div class="level-right is-marginless"><p class="sponsors level-item is-marginless"><span id="support-ack-url">We gratefully acknowledge support from<br /> the Simons Foundation, <a href="https://info.arxiv.org/about/ourmembers.html">member institutions</a>, and all contributors. <a href="https://info.arxiv.org/about/donate.html">Donate</a></span></p></div> </div>  <div class="identity level is-marginless"> <div class="level-left"> <div class="level-item"> <a class="arxiv" href="https://arxiv.org/" aria-label="arxiv-logo"> <img src="https://static.arxiv.org/static/base/1.0.0a5/images/arxiv-logo-one-color-white.svg" aria-label="logo" alt="arxiv logo" width="85" style="width:85px;"/> </a> </div> </div> <div class="search-block level-right"> <form class="level-item mini-search" method="GET" action="https://arxiv.org/search"> <div class="field has-addons"> <div class="control"> <input class="input is-small" type="text" name="query" placeholder="Search..." aria-label="Search term or terms" /> <p class="help"><a href="https://info.arxiv.org/help">Help</a> | <a href="https://arxiv.org/search/advanced">Advanced Search</a></p> </div> <div class="control"> <div class="select is-small"> <select name="searchtype" aria-label="Field to search"> <option value="all" selected="selected">All fields</option> <option value="title">Title</option> <option value="author">Author</option> <option value="abstract">Abstract</option> <option value="comments">Comments</option> <option value="journal_ref">Journal reference</option> <option value="acm_class">ACM classification</option> <option value="msc_class">MSC classification</option> <option value="report_num">Report number</option> <option value="paper_id">arXiv identifier</option> <option value="doi">DOI</option> <option value="orcid">ORCID</option> <option value="author_id">arXiv author ID</option> <option value="help">Help pages</option> <option value="full_text">Full text</option> </select> </div> </div> <input type="hidden" name="source" value="header"> <button class="button is-small is-cul-darker">Search</button> </div> </form> </div> </div>  <div class="container"> <div class="user-tools is-size-7 has-text-right has-text-weight-bold" role="navigation" aria-label="User menu"> <a href="https://arxiv.org/login">Login</a> </div> </div> </header> <main class="container" id="main-container"> <div class="level is-marginless"> <div class="level-left"> <h1 class="title is-clearfix"> Showing 1–41 of 41 results for author: <span class="mathjax">Friedman, R</span> </h1> </div> <div class="level-right is-hidden-mobile">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> <div class="content"> <form method="GET" action="/search/cs" aria-role="search"> Searching in archive <strong>cs</strong>. <a href="/search/?searchtype=author&query=Friedman%2C+R">Search in all archives.</a> <div class="field has-addons-tablet"> <div class="control is-expanded"> <label for="query" class="hidden-label">Search term or terms</label> <input class="input is-medium" id="query" name="query" placeholder="Search term..." type="text" value="Friedman, R"> </div> <div class="select control is-medium"> <label class="is-hidden" for="searchtype">Field</label> <select class="is-medium" id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> </div> <div class="control"> <button class="button is-link is-medium">Search</button> </div> </div> <div class="field"> <div class="control is-size-7"> <label class="radio"> <input checked id="abstracts-0" name="abstracts" type="radio" value="show"> Show abstracts </label> <label class="radio"> <input id="abstracts-1" name="abstracts" type="radio" value="hide"> Hide abstracts </label> </div> </div> <div class="is-clearfix" style="height: 2.5em"> <div class="is-pulled-right"> <a href="/search/advanced?terms-0-term=Friedman%2C+R&terms-0-field=author&size=50&order=-announced_date_first">Advanced Search</a> </div> </div> <input type="hidden" name="order" value="-announced_date_first"> <input type="hidden" name="size" value="50"> </form> <div class="level breathe-horizontal"> <div class="level-left"> <form method="GET" action="/search/"> <div style="display: none;"> <select id="searchtype" name="searchtype"><option value="all">All fields</option><option value="title">Title</option><option selected value="author">Author(s)</option><option value="abstract">Abstract</option><option value="comments">Comments</option><option value="journal_ref">Journal reference</option><option value="acm_class">ACM classification</option><option value="msc_class">MSC classification</option><option value="report_num">Report number</option><option value="paper_id">arXiv identifier</option><option value="doi">DOI</option><option value="orcid">ORCID</option><option value="license">License (URI)</option><option value="author_id">arXiv author ID</option><option value="help">Help pages</option><option value="full_text">Full text</option></select> <input id="query" name="query" type="text" value="Friedman, R"> <ul id="abstracts"><li><input checked id="abstracts-0" name="abstracts" type="radio" value="show"> <label for="abstracts-0">Show abstracts</label></li><li><input id="abstracts-1" name="abstracts" type="radio" value="hide"> <label for="abstracts-1">Hide abstracts</label></li></ul> </div> <div class="box field is-grouped is-grouped-multiline level-item"> <div class="control"> <span class="select is-small"> <select id="size" name="size"><option value="25">25</option><option selected value="50">50</option><option value="100">100</option><option value="200">200</option></select> </span> <label for="size">results per page</label>. </div> <div class="control"> <label for="order">Sort results by</label> <span class="select is-small"> <select id="order" name="order"><option selected value="-announced_date_first">Announcement date (newest first)</option><option value="announced_date_first">Announcement date (oldest first)</option><option value="-submitted_date">Submission date (newest first)</option><option value="submitted_date">Submission date (oldest first)</option><option value="">Relevance</option></select> </span> </div> <div class="control"> <button class="button is-small is-link">Go</button> </div> </div> </form> </div> </div> <ol class="breathe-horizontal" start="1"> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2409.07940">arXiv:2409.07940</a> <span> [<a href="https://arxiv.org/pdf/2409.07940">pdf</a>, <a href="https://arxiv.org/format/2409.07940">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> Control+Shift: Generating Controllable Distribution Shifts </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Chowers%2C+R">Rhea Chowers</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2409.07940v1-abstract-short" style="display: inline;"> We propose a new method for generating realistic datasets with distribution shifts using any decoder-based generative model. Our approach systematically creates datasets with varying intensities of distribution shifts, facilitating a comprehensive analysis of model performance degradation. We then use these generated datasets to evaluate the performance of various commonly used networks and observ… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.07940v1-abstract-full').style.display = 'inline'; document.getElementById('2409.07940v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2409.07940v1-abstract-full" style="display: none;"> We propose a new method for generating realistic datasets with distribution shifts using any decoder-based generative model. Our approach systematically creates datasets with varying intensities of distribution shifts, facilitating a comprehensive analysis of model performance degradation. We then use these generated datasets to evaluate the performance of various commonly used networks and observe a consistent decline in performance with increasing shift intensity, even when the effect is almost perceptually unnoticeable to the human eye. We see this degradation even when using data augmentations. We also find that enlarging the training dataset beyond a certain point has no effect on the robustness and that stronger inductive biases increase robustness. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2409.07940v1-abstract-full').style.display = 'none'; document.getElementById('2409.07940v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 September, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">ECCV2024, "Synthetic Data for Computer Vision" workshop</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2407.21037">arXiv:2407.21037</a> <span> [<a href="https://arxiv.org/pdf/2407.21037">pdf</a>, <a href="https://arxiv.org/format/2407.21037">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Artificial Intelligence">cs.AI</span> </div> </div> <p class="title is-5 mathjax"> An Application of Large Language Models to Coding Negotiation Transcripts </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Ray Friedman</a>, <a href="/search/cs?searchtype=author&query=Cho%2C+J">Jaewoo Cho</a>, <a href="/search/cs?searchtype=author&query=Brett%2C+J">Jeanne Brett</a>, <a href="/search/cs?searchtype=author&query=Zhan%2C+X">Xuhui Zhan</a>, <a href="/search/cs?searchtype=author&query=Han%2C+N">Ningyu Han</a>, <a href="/search/cs?searchtype=author&query=Kannan%2C+S">Sriram Kannan</a>, <a href="/search/cs?searchtype=author&query=Ma%2C+Y">Yingxiang Ma</a>, <a href="/search/cs?searchtype=author&query=Spencer-Smith%2C+J">Jesse Spencer-Smith</a>, <a href="/search/cs?searchtype=author&query=J%C3%A4ckel%2C+E">Elisabeth J盲ckel</a>, <a href="/search/cs?searchtype=author&query=Zerres%2C+A">Alfred Zerres</a>, <a href="/search/cs?searchtype=author&query=Hooper%2C+M">Madison Hooper</a>, <a href="/search/cs?searchtype=author&query=Babbit%2C+K">Katie Babbit</a>, <a href="/search/cs?searchtype=author&query=Acharya%2C+M">Manish Acharya</a>, <a href="/search/cs?searchtype=author&query=Adair%2C+W">Wendi Adair</a>, <a href="/search/cs?searchtype=author&query=Aslani%2C+S">Soroush Aslani</a>, <a href="/search/cs?searchtype=author&query=Ayka%C3%A7%2C+T">Tayfun Ayka莽</a>, <a href="/search/cs?searchtype=author&query=Bauman%2C+C">Chris Bauman</a>, <a href="/search/cs?searchtype=author&query=Bennett%2C+R">Rebecca Bennett</a>, <a href="/search/cs?searchtype=author&query=Brady%2C+G">Garrett Brady</a>, <a href="/search/cs?searchtype=author&query=Briggs%2C+P">Peggy Briggs</a>, <a href="/search/cs?searchtype=author&query=Dowie%2C+C">Cheryl Dowie</a>, <a href="/search/cs?searchtype=author&query=Eck%2C+C">Chase Eck</a>, <a href="/search/cs?searchtype=author&query=Geiger%2C+I">Igmar Geiger</a>, <a href="/search/cs?searchtype=author&query=Jacob%2C+F">Frank Jacob</a>, <a href="/search/cs?searchtype=author&query=Kern%2C+M">Molly Kern</a> , et al. (33 additional authors not shown) </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2407.21037v1-abstract-short" style="display: inline;"> In recent years, Large Language Models (LLM) have demonstrated impressive capabilities in the field of natural language processing (NLP). This paper explores the application of LLMs in negotiation transcript analysis by the Vanderbilt AI Negotiation Lab. Starting in September 2022, we applied multiple strategies using LLMs from zero shot learning to fine tuning models to in-context learning). The… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.21037v1-abstract-full').style.display = 'inline'; document.getElementById('2407.21037v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2407.21037v1-abstract-full" style="display: none;"> In recent years, Large Language Models (LLM) have demonstrated impressive capabilities in the field of natural language processing (NLP). This paper explores the application of LLMs in negotiation transcript analysis by the Vanderbilt AI Negotiation Lab. Starting in September 2022, we applied multiple strategies using LLMs from zero shot learning to fine tuning models to in-context learning). The final strategy we developed is explained, along with how to access and use the model. This study provides a sense of both the opportunities and roadblocks for the implementation of LLMs in real life applications and offers a model for how LLMs can be applied to coding in other fields. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2407.21037v1-abstract-full').style.display = 'none'; document.getElementById('2407.21037v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 July, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.14098">arXiv:2402.14098</a> <span> [<a href="https://arxiv.org/pdf/2402.14098">pdf</a>, <a href="https://arxiv.org/format/2402.14098">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> </div> </div> <p class="title is-5 mathjax"> Intriguing Properties of Modern GANs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Weiss%2C+Y">Yair Weiss</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.14098v1-abstract-short" style="display: inline;"> Modern GANs achieve remarkable performance in terms of generating realistic and diverse samples. This has led many to believe that ``GANs capture the training data manifold''. In this work we show that this interpretation is wrong. We empirically show that the manifold learned by modern GANs does not fit the training distribution: specifically the manifold does not pass through the training exampl… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.14098v1-abstract-full').style.display = 'inline'; document.getElementById('2402.14098v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.14098v1-abstract-full" style="display: none;"> Modern GANs achieve remarkable performance in terms of generating realistic and diverse samples. This has led many to believe that ``GANs capture the training data manifold''. In this work we show that this interpretation is wrong. We empirically show that the manifold learned by modern GANs does not fit the training distribution: specifically the manifold does not pass through the training examples and passes closer to out-of-distribution images than to in-distribution images. We also investigate the distribution over images implied by the prior over the latent codes and study whether modern GANs learn a density that approximates the training distribution. Surprisingly, we find that the learned density is very far from the data distribution and that GANs tend to assign higher density to out-of-distribution images. Finally, we demonstrate that the set of images used to train modern GANs are often not part of the typical set described by the GANs' distribution. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.14098v1-abstract-full').style.display = 'none'; document.getElementById('2402.14098v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 21 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2402.05535">arXiv:2402.05535</a> <span> [<a href="https://arxiv.org/pdf/2402.05535">pdf</a>, <a href="https://arxiv.org/format/2402.05535">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Batch-Schedule-Execute: On Optimizing Concurrent Deterministic Scheduling for Blockchains (Extended Version) </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Hay%2C+Y">Yaron Hay</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2402.05535v2-abstract-short" style="display: inline;"> Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain's performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs' execution runtime. A unique challenge of blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.05535v2-abstract-full').style.display = 'inline'; document.getElementById('2402.05535v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2402.05535v2-abstract-full" style="display: none;"> Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain's performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs' execution runtime. A unique challenge of blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order to maintain the semantics of State Machine Replication (SMR). In this work, we study the maximal level of parallelism attainable when focusing on the conflict graph between transactions packaged in the same block. This exposes a performance vulnerability that block creators may exploit against existing blockchain concurrency solutions, which rely on a total ordering phase for maintaining consistency amongst all replicas. To facilitate the formal aspects of our study, we develop a novel generic framework for Active State Machine Replication (ASMR) that is strictly serializable. We introduce the concept of graph scheduling and the definition of the minimal latency scheduling problem, which we prove to be NP-hard. We show that the restricted version of this problem for homogeneous transactions is equivalent to the classic Graph Vertex Coloring Problem, yet show that the heterogeneous case is more complex. We discuss the practical implications of these results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2402.05535v2-abstract-full').style.display = 'none'; document.getElementById('2402.05535v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 August, 2024; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 February, 2024; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> February 2024. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Updated version for conference version; 53 pages, 12 figures, LaTeX with Auxiliary Files, short single line</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2309.03045">arXiv:2309.03045</a> <span> [<a href="https://arxiv.org/pdf/2309.03045">pdf</a>, <a href="https://arxiv.org/format/2309.03045">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> An Evaluation of Software Sketches </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2309.03045v1-abstract-short" style="display: inline;"> This work presents a detailed evaluation of Rust (software) implementations of several popular sketching solutions, as well as recently proposed optimizations. We compare these solutions in terms of computational speed, memory consumption, and several approximation error metrics. Overall, we find a simple hashing based solution employed with the Nitro sampling technique [22] gives the best trade-o… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.03045v1-abstract-full').style.display = 'inline'; document.getElementById('2309.03045v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2309.03045v1-abstract-full" style="display: none;"> This work presents a detailed evaluation of Rust (software) implementations of several popular sketching solutions, as well as recently proposed optimizations. We compare these solutions in terms of computational speed, memory consumption, and several approximation error metrics. Overall, we find a simple hashing based solution employed with the Nitro sampling technique [22] gives the best trade-off between memory, error and speed. Our findings also include some novel insights about how to best combine sampling with Counting Cuckoo filters depending on the application. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2309.03045v1-abstract-full').style.display = 'none'; document.getElementById('2309.03045v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 September, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2023. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2305.01628">arXiv:2305.01628</a> <span> [<a href="https://arxiv.org/pdf/2305.01628">pdf</a>, <a href="https://arxiv.org/format/2305.01628">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Machine Learning">cs.LG</span> </div> </div> <p class="title is-5 mathjax"> The Benefits of Bad Advice: Autocontrastive Decoding across Model Layers </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gera%2C+A">Ariel Gera</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Arviv%2C+O">Ofir Arviv</a>, <a href="/search/cs?searchtype=author&query=Gunasekara%2C+C">Chulaka Gunasekara</a>, <a href="/search/cs?searchtype=author&query=Sznajder%2C+B">Benjamin Sznajder</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a>, <a href="/search/cs?searchtype=author&query=Shnarch%2C+E">Eyal Shnarch</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2305.01628v1-abstract-short" style="display: inline;"> Applying language models to natural language processing tasks typically relies on the representations in the final model layer, as intermediate hidden layer representations are presumed to be less informative. In this work, we argue that due to the gradual improvement across model layers, additional information can be gleaned from the contrast between higher and lower layers during inference. Spec… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.01628v1-abstract-full').style.display = 'inline'; document.getElementById('2305.01628v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2305.01628v1-abstract-full" style="display: none;"> Applying language models to natural language processing tasks typically relies on the representations in the final model layer, as intermediate hidden layer representations are presumed to be less informative. In this work, we argue that due to the gradual improvement across model layers, additional information can be gleaned from the contrast between higher and lower layers during inference. Specifically, in choosing between the probable next token predictions of a generative model, the predictions of lower layers can be used to highlight which candidates are best avoided. We propose a novel approach that utilizes the contrast between layers to improve text generation outputs, and show that it mitigates degenerative behaviors of the model in open-ended generation, significantly improving the quality of generated texts. Furthermore, our results indicate that contrasting between model layers at inference time can yield substantial benefits to certain aspects of general language model capabilities, more effectively extracting knowledge during inference from a given set of model parameters. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2305.01628v1-abstract-full').style.display = 'none'; document.getElementById('2305.01628v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 May, 2023; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2023. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">9 pages, 8 figures; To be published in ACL 2023</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2206.13367">arXiv:2206.13367</a> <span> [<a href="https://arxiv.org/pdf/2206.13367">pdf</a>, <a href="https://arxiv.org/format/2206.13367">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Operating Systems">cs.OS</span> </div> </div> <p class="title is-5 mathjax"> Multilevel Bidirectional Cache Filter </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Eytan%2C+O">Ohad Eytan</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2206.13367v1-abstract-short" style="display: inline;"> Modern caches are often required to handle a massive amount of data, which exceeds the amount of available memory; thus, hybrid caches, specifically DRAM/SSD combination, become more and more prevalent. In such environments, in addition to the classical hit-ratio target, saving writes to the second-level cache is a dominant factor to avoid write amplification and wear out, two notorious phenomena… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.13367v1-abstract-full').style.display = 'inline'; document.getElementById('2206.13367v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2206.13367v1-abstract-full" style="display: none;"> Modern caches are often required to handle a massive amount of data, which exceeds the amount of available memory; thus, hybrid caches, specifically DRAM/SSD combination, become more and more prevalent. In such environments, in addition to the classical hit-ratio target, saving writes to the second-level cache is a dominant factor to avoid write amplification and wear out, two notorious phenomena of SSD. This paper presents BiDiFilter, a novel multilevel caching scheme that controls demotions and promotions between cache levels using a frequency sketch filter. Further, it splits the higher cache level into two areas to keep the most recent and the most frequent items close to the user. We conduct an extensive evaluation over real-world traces, comparing to previous multilevel policies. We show that using our mechanism yields an x10 saving of writes in almost all cases and often improving latencies by up to 20%. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2206.13367v1-abstract-full').style.display = 'none'; document.getElementById('2206.13367v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 27 June, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2205.12240">arXiv:2205.12240</a> <span> [<a href="https://arxiv.org/pdf/2205.12240">pdf</a>, <a href="https://arxiv.org/format/2205.12240">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> VIRATrustData: A Trust-Annotated Corpus of Human-Chatbot Conversations About COVID-19 Vaccines </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Sedoc%2C+J">Jo茫o Sedoc</a>, <a href="/search/cs?searchtype=author&query=Gretz%2C+S">Shai Gretz</a>, <a href="/search/cs?searchtype=author&query=Toledo%2C+A">Assaf Toledo</a>, <a href="/search/cs?searchtype=author&query=Weeks%2C+R">Rose Weeks</a>, <a href="/search/cs?searchtype=author&query=Bar-Zeev%2C+N">Naor Bar-Zeev</a>, <a href="/search/cs?searchtype=author&query=Katz%2C+Y">Yoav Katz</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2205.12240v1-abstract-short" style="display: inline;"> Public trust in medical information is crucial for successful application of public health policies such as vaccine uptake. This is especially true when the information is offered remotely, by chatbots, which have become increasingly popular in recent years. Here, we explore the challenging task of human-bot turn-level trust classification. We rely on a recently released data of observationally-co… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.12240v1-abstract-full').style.display = 'inline'; document.getElementById('2205.12240v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2205.12240v1-abstract-full" style="display: none;"> Public trust in medical information is crucial for successful application of public health policies such as vaccine uptake. This is especially true when the information is offered remotely, by chatbots, which have become increasingly popular in recent years. Here, we explore the challenging task of human-bot turn-level trust classification. We rely on a recently released data of observationally-collected (rather than crowdsourced) dialogs with VIRA chatbot, a COVID-19 Vaccine Information Resource Assistant. These dialogs are centered around questions and concerns about COVID-19 vaccines, where trust is particularly acute. We annotated $3k$ VIRA system-user conversational turns for Low Institutional Trust or Low Agent Trust vs. Neutral or High Trust. We release the labeled dataset, VIRATrustData, the first of its kind to the best of our knowledge. We demonstrate how this task is non-trivial and compare several models that predict the different levels of trust. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.12240v1-abstract-full').style.display = 'none'; document.getElementById('2205.12240v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 May, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2205.11966">arXiv:2205.11966</a> <span> [<a href="https://arxiv.org/pdf/2205.11966">pdf</a>, <a href="https://arxiv.org/format/2205.11966">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Benchmark Data and Evaluation Framework for Intent Discovery Around COVID-19 Vaccine Hesitancy </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gretz%2C+S">Shai Gretz</a>, <a href="/search/cs?searchtype=author&query=Toledo%2C+A">Assaf Toledo</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Lahav%2C+D">Dan Lahav</a>, <a href="/search/cs?searchtype=author&query=Weeks%2C+R">Rose Weeks</a>, <a href="/search/cs?searchtype=author&query=Bar-Zeev%2C+N">Naor Bar-Zeev</a>, <a href="/search/cs?searchtype=author&query=Sedoc%2C+J">Jo茫o Sedoc</a>, <a href="/search/cs?searchtype=author&query=Sangha%2C+P">Pooja Sangha</a>, <a href="/search/cs?searchtype=author&query=Katz%2C+Y">Yoav Katz</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2205.11966v2-abstract-short" style="display: inline;"> The COVID-19 pandemic has made a huge global impact and cost millions of lives. As COVID-19 vaccines were rolled out, they were quickly met with widespread hesitancy. To address the concerns of hesitant people, we launched VIRA, a public dialogue system aimed at addressing questions and concerns surrounding the COVID-19 vaccines. Here, we release VIRADialogs, a dataset of over 8k dialogues conduct… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.11966v2-abstract-full').style.display = 'inline'; document.getElementById('2205.11966v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2205.11966v2-abstract-full" style="display: none;"> The COVID-19 pandemic has made a huge global impact and cost millions of lives. As COVID-19 vaccines were rolled out, they were quickly met with widespread hesitancy. To address the concerns of hesitant people, we launched VIRA, a public dialogue system aimed at addressing questions and concerns surrounding the COVID-19 vaccines. Here, we release VIRADialogs, a dataset of over 8k dialogues conducted by actual users with VIRA, providing a unique real-world conversational dataset. In light of rapid changes in users' intents, due to updates in guidelines or in response to new information, we highlight the important task of intent discovery in this use-case. We introduce a novel automatic evaluation framework for intent discovery, leveraging the existing intent classifier of VIRA. We use this framework to report baseline intent discovery results over VIRADialogs, that highlight the difficulty of this task. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2205.11966v2-abstract-full').style.display = 'none'; document.getElementById('2205.11966v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 October, 2022; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 May, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2203.04803">arXiv:2203.04803</a> <span> [<a href="https://arxiv.org/pdf/2203.04803">pdf</a>, <a href="https://arxiv.org/format/2203.04803">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Operating Systems">cs.OS</span> </div> </div> <p class="title is-5 mathjax"> Limited Associativity Caching in the Data Plane </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Goaz%2C+O">Or Goaz</a>, <a href="/search/cs?searchtype=author&query=Hovav%2C+D">Dor Hovav</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2203.04803v1-abstract-short" style="display: inline;"> In-network caching promises to improve the performance of networked and edge applications as it shortens the paths data need to travel. This is by storing so-called hot items in the network switches on-route between clients who access the data and the storage servers who maintain it. Since the data flows through those switches in any case, it is natural to cache hot items there. Most software-ma… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.04803v1-abstract-full').style.display = 'inline'; document.getElementById('2203.04803v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2203.04803v1-abstract-full" style="display: none;"> In-network caching promises to improve the performance of networked and edge applications as it shortens the paths data need to travel. This is by storing so-called hot items in the network switches on-route between clients who access the data and the storage servers who maintain it. Since the data flows through those switches in any case, it is natural to cache hot items there. Most software-managed caches treat the cache as a fully associative region. Alas, a fully associative design seems to be at odds with programmable switches' goal of handling packets in a short bounded amount of time, as well as their restricted programming model. In this work, we present PKache, a generic limited associativity cache implementation in the programmable switches' domain-specific P4 language, and demonstrate its utility by realizing multiple popular cache management schemes. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2203.04803v1-abstract-full').style.display = 'none'; document.getElementById('2203.04803v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 March, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2201.01958">arXiv:2201.01958</a> <span> [<a href="https://arxiv.org/pdf/2201.01958">pdf</a>, <a href="https://arxiv.org/format/2201.01958">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> SQUAD: Combining Sketching and Sampling Is Better than Either for Per-item Quantile Estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Shahout%2C+R">Rana Shahout</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2201.01958v1-abstract-short" style="display: inline;"> Stream monitoring is fundamental in many data stream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often capture the user's utility. For example, if a video connection has high tail latency, the perceived quality will suffer, even if the average and median latencies are low. In this w… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2201.01958v1-abstract-full').style.display = 'inline'; document.getElementById('2201.01958v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2201.01958v1-abstract-full" style="display: none;"> Stream monitoring is fundamental in many data stream applications, such as financial data trackers, security, anomaly detection, and load balancing. In that respect, quantiles are of particular interest, as they often capture the user's utility. For example, if a video connection has high tail latency, the perceived quality will suffer, even if the average and median latencies are low. In this work, we consider the problem of approximating the per-item quantiles. Elements in our stream are (ID, latency) tuples, and we wish to track the latency quantiles for each ID. Existing quantile sketches are designed for a single number stream (e.g., containing just the latency). While one could allocate a separate sketch instance for each ID, this may require an infeasible amount of memory. Instead, we consider tracking the quantiles for the heavy hitters (most frequent items), which are often considered particularly important, without knowing them beforehand. We first present a simple sampling algorithm that serves as a benchmark. Then, we design an algorithm that augments a quantile sketch within each entry of a heavy hitter algorithm, resulting in similar space complexity but with a deterministic error guarantee. Finally, we present SQUAD, a method that combines sampling and sketching while improving the asymptotic space complexity. Intuitively, SQUAD uses a background sampling process to capture the behaviour of the latencies of an item before it is allocated with a sketch, thereby allowing us to use fewer samples and sketches. Our solutions are rigorously analyzed, and we demonstrate the superiority of our approach using extensive simulations. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2201.01958v1-abstract-full').style.display = 'none'; document.getElementById('2201.01958v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 6 January, 2022; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2022. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2110.10577">arXiv:2110.10577</a> <span> [<a href="https://arxiv.org/pdf/2110.10577">pdf</a>, <a href="https://arxiv.org/format/2110.10577">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Overview of the 2021 Key Point Analysis Shared Task </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Dankin%2C+L">Lena Dankin</a>, <a href="/search/cs?searchtype=author&query=Hou%2C+Y">Yufang Hou</a>, <a href="/search/cs?searchtype=author&query=Aharonov%2C+R">Ranit Aharonov</a>, <a href="/search/cs?searchtype=author&query=Katz%2C+Y">Yoav Katz</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2110.10577v1-abstract-short" style="display: inline;"> We describe the 2021 Key Point Analysis (KPA-2021) shared task on key point analysis that we organized as a part of the 8th Workshop on Argument Mining (ArgMining 2021) at EMNLP 2021. We outline various approaches and discuss the results of the shared task. We expect the task and the findings reported in this paper to be relevant for researchers working on text summarization and argument mining. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2110.10577v1-abstract-full" style="display: none;"> We describe the 2021 Key Point Analysis (KPA-2021) shared task on key point analysis that we organized as a part of the 8th Workshop on Argument Mining (ArgMining 2021) at EMNLP 2021. We outline various approaches and discuss the results of the shared task. We expect the task and the findings reported in this paper to be relevant for researchers working on text summarization and argument mining. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2110.10577v1-abstract-full').style.display = 'none'; document.getElementById('2110.10577v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 October, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2109.03021">arXiv:2109.03021</a> <span> [<a href="https://arxiv.org/pdf/2109.03021">pdf</a>, <a href="https://arxiv.org/format/2109.03021">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Hardware Architecture">cs.AR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> Limited Associativity Makes Concurrent Software Caches a Breeze </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Adas%2C+D">Dolev Adas</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2109.03021v1-abstract-short" style="display: inline;"> Software caches optimize the performance of diverse storage systems, databases and other software systems. Existing works on software caches automatically resort to fully associative cache designs. Our work shows that limited associativity caches are a promising direction for concurrent software caches. Specifically, we demonstrate that limited associativity enables simple yet efficient realizatio… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2109.03021v1-abstract-full').style.display = 'inline'; document.getElementById('2109.03021v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2109.03021v1-abstract-full" style="display: none;"> Software caches optimize the performance of diverse storage systems, databases and other software systems. Existing works on software caches automatically resort to fully associative cache designs. Our work shows that limited associativity caches are a promising direction for concurrent software caches. Specifically, we demonstrate that limited associativity enables simple yet efficient realizations of multiple cache management schemes that can be trivially parallelized. We show that the obtained hit ratio is usually similar to fully associative caches of the same management policy, but the throughput is improved by up to X5 compared to production-grade caching libraries, especially in multi-threaded executions. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2109.03021v1-abstract-full').style.display = 'none'; document.getElementById('2109.03021v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 19 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2108.12287">arXiv:2108.12287</a> <span> [<a href="https://arxiv.org/pdf/2108.12287">pdf</a>, <a href="https://arxiv.org/ps/2108.12287">ps</a>, <a href="https://arxiv.org/format/2108.12287">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computers and Society">cs.CY</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Applications">stat.AP</span> </div> </div> <p class="title is-5 mathjax"> Evaluation of individual attributes associated with shared HIV risk behaviors among two network-based studies of people who inject drugs </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Ryan%2C+V">Valerie Ryan</a>, <a href="/search/cs?searchtype=author&query=Lee%2C+T">TingFang Lee</a>, <a href="/search/cs?searchtype=author&query=Buchanan%2C+A+L">Ashley L. Buchanan</a>, <a href="/search/cs?searchtype=author&query=Katenka%2C+N+V">Natallia V. Katenka</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+S+R">Samuel R. Friedman</a>, <a href="/search/cs?searchtype=author&query=Nikolopoulos%2C+G">Georgios Nikolopoulos</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2108.12287v1-abstract-short" style="display: inline;"> Social context plays an important role in perpetuating or reducing HIV risk behaviors. This study analyzed the network and individual attributes that were associated with the likelihood that people who inject drugs (PWID) will engage in HIV risk behaviors with one another. We analyze data collected in the Social Risk Factors and HIV Risk Study (SFHR) and Transmission Reduction Intervention Project… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.12287v1-abstract-full').style.display = 'inline'; document.getElementById('2108.12287v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2108.12287v1-abstract-full" style="display: none;"> Social context plays an important role in perpetuating or reducing HIV risk behaviors. This study analyzed the network and individual attributes that were associated with the likelihood that people who inject drugs (PWID) will engage in HIV risk behaviors with one another. We analyze data collected in the Social Risk Factors and HIV Risk Study (SFHR) and Transmission Reduction Intervention Project (TRIP) to perform the analysis. Exponential random graph models were used to determine which attributes were associated with the likelihood of people engaging in HIV risk behaviors, such as injection behaviors that are associated with one another, among PWID. Results across all models and across both data sets indicated that people were more likely to engage in risk behaviors with others who were similar to them in some way (e.g., were the same sex, race/ethnicity, living conditions). In both SFHR and TRIP, we explore the effects of missingness at individual and network levels on the likelihood of individuals to engage in HIV risk behaviors among PWID. In this study, we found that known individual-level risk factors, including housing instability and race/ethnicity, are also important factors in determining the structure of the observed network among PWID. Future development of interventions should consider not only individual risk factors, but communities and social influences leaving individuals vulnerable to HIV risk. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2108.12287v1-abstract-full').style.display = 'none'; document.getElementById('2108.12287v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 18 August, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">19 pages</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2107.12788">arXiv:2107.12788</a> <span> [<a href="https://arxiv.org/pdf/2107.12788">pdf</a>, <a href="https://arxiv.org/format/2107.12788">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> On the data persistency of replicated erasure codes in distributed storage systems </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Kapelko%2C+R">Rafa艂 Kapelko</a>, <a href="/search/cs?searchtype=author&query=Marchwicki%2C+K">Karol Marchwicki</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2107.12788v1-abstract-short" style="display: inline;"> This paper studies the fundamental problem of data persistency for a general family of redundancy schemes in distributed storage systems, called replicated erasure codes. Namely, we analyze two strategies of replicated erasure codes distribution: random and symmetric. For both strategies we derive closed analytical and asymptotic formulas for expected data persistency despite nodes failure. </span> <span class="abstract-full has-text-grey-dark mathjax" id="2107.12788v1-abstract-full" style="display: none;"> This paper studies the fundamental problem of data persistency for a general family of redundancy schemes in distributed storage systems, called replicated erasure codes. Namely, we analyze two strategies of replicated erasure codes distribution: random and symmetric. For both strategies we derive closed analytical and asymptotic formulas for expected data persistency despite nodes failure. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2107.12788v1-abstract-full').style.display = 'none'; document.getElementById('2107.12788v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 27 July, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2106.06758">arXiv:2106.06758</a> <span> [<a href="https://arxiv.org/pdf/2106.06758">pdf</a>, <a href="https://arxiv.org/format/2106.06758">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Every Bite Is an Experience: Key Point Analysis of Business Reviews </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bar-Haim%2C+R">Roy Bar-Haim</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+L">Lilach Eden</a>, <a href="/search/cs?searchtype=author&query=Kantor%2C+Y">Yoav Kantor</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2106.06758v1-abstract-short" style="display: inline;"> Previous work on review summarization focused on measuring the sentiment toward the main aspects of the reviewed product or business, or on creating a textual summary. These approaches provide only a partial view of the data: aspect-based sentiment summaries lack sufficient explanation or justification for the aspect rating, while textual summaries do not quantify the significance of each element,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.06758v1-abstract-full').style.display = 'inline'; document.getElementById('2106.06758v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2106.06758v1-abstract-full" style="display: none;"> Previous work on review summarization focused on measuring the sentiment toward the main aspects of the reviewed product or business, or on creating a textual summary. These approaches provide only a partial view of the data: aspect-based sentiment summaries lack sufficient explanation or justification for the aspect rating, while textual summaries do not quantify the significance of each element, and are not well-suited for representing conflicting views. Recently, Key Point Analysis (KPA) has been proposed as a summarization framework that provides both textual and quantitative summary of the main points in the data. We adapt KPA to review data by introducing Collective Key Point Mining for better key point extraction; integrating sentiment analysis into KPA; identifying good key point candidates for review summaries; and leveraging the massive amount of available reviews and their metadata. We show empirically that these novel extensions of KPA substantially improve its performance. We demonstrate that promising results can be achieved without any domain-specific annotation, while human supervision can lead to further improvement. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2106.06758v1-abstract-full').style.display = 'none'; document.getElementById('2106.06758v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 12 June, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2021. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">ACL-IJCNLP 2021</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2105.08770">arXiv:2105.08770</a> <span> [<a href="https://arxiv.org/pdf/2105.08770">pdf</a>, <a href="https://arxiv.org/format/2105.08770">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Operating Systems">cs.OS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> </div> </div> <p class="title is-5 mathjax"> Lightweight Robust Size Aware Cache Management </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Eytan%2C+O">Ohad Eytan</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Manes%2C+B">Benjamin Manes</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2105.08770v2-abstract-short" style="display: inline;"> Modern key-value stores, object stores, Internet proxy caches, as well as Content Delivery Networks (CDN) often manage objects of diverse sizes, e.g., blobs, video files of different lengths, images with varying resolution, and small documents. In such workloads, size-aware cache policies outperform size-oblivious algorithms. Unfortunately, existing size-aware algorithms tend to be overly complica… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.08770v2-abstract-full').style.display = 'inline'; document.getElementById('2105.08770v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2105.08770v2-abstract-full" style="display: none;"> Modern key-value stores, object stores, Internet proxy caches, as well as Content Delivery Networks (CDN) often manage objects of diverse sizes, e.g., blobs, video files of different lengths, images with varying resolution, and small documents. In such workloads, size-aware cache policies outperform size-oblivious algorithms. Unfortunately, existing size-aware algorithms tend to be overly complicated and computationally~expensive. Our work follows a more approachable pattern; we extend the prevalent (size-oblivious) TinyLFU cache admission policy to handle variable sized items. Implementing our approach inside two popular caching libraries only requires minor changes. We show that our algorithms yield competitive or better hit-ratios and byte hit-ratios compared to the state of the art size-aware algorithms such as AdaptSize, LHD, LRB, and GDSF. Further, a runtime comparison indicates that our implementation is faster by up to x3 compared to the best alternative, i.e., it imposes much lower CPU overhead. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2105.08770v2-abstract-full').style.display = 'none'; document.getElementById('2105.08770v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 23 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 18 May, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2104.09895">arXiv:2104.09895</a> <span> [<a href="https://arxiv.org/pdf/2104.09895">pdf</a>, <a href="https://arxiv.org/format/2104.09895">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computer Vision and Pattern Recognition">cs.CV</span> </div> </div> <p class="title is-5 mathjax"> Posterior Sampling for Image Restoration using Explicit Patch Priors </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Weiss%2C+Y">Yair Weiss</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2104.09895v1-abstract-short" style="display: inline;"> Almost all existing methods for image restoration are based on optimizing the mean squared error (MSE), even though it is known that the best estimate in terms of MSE may yield a highly atypical image due to the fact that there are many plausible restorations for a given noisy image. In this paper, we show how to combine explicit priors on patches of natural images in order to sample from the post… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2104.09895v1-abstract-full').style.display = 'inline'; document.getElementById('2104.09895v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2104.09895v1-abstract-full" style="display: none;"> Almost all existing methods for image restoration are based on optimizing the mean squared error (MSE), even though it is known that the best estimate in terms of MSE may yield a highly atypical image due to the fact that there are many plausible restorations for a given noisy image. In this paper, we show how to combine explicit priors on patches of natural images in order to sample from the posterior probability of a full image given a degraded image. We prove that our algorithm generates correct samples from the distribution $p(x|y) \propto \exp(-E(x|y))$ where $E(x|y)$ is the cost function minimized in previous patch-based approaches that compute a single restoration. Unlike previous approaches that computed a single restoration using MAP or MMSE, our method makes explicit the uncertainty in the restored images and guarantees that all patches in the restored images will be typical given the patch prior. Unlike previous approaches that used implicit priors on fixed-size images, our approach can be used with images of any size. Our experimental results show that posterior sampling using patch priors yields images of high perceptual quality and high PSNR on a range of challenging image restoration problems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2104.09895v1-abstract-full').style.display = 'none'; document.getElementById('2104.09895v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 20 April, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2103.14071">arXiv:2103.14071</a> <span> [<a href="https://arxiv.org/pdf/2103.14071">pdf</a>, <a href="https://arxiv.org/format/2103.14071">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> Accelerating Big-Data Sorting Through Programmable Switches </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Barshatz-Schneor%2C+Y">Yamit Barshatz-Schneor</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2103.14071v1-abstract-short" style="display: inline;"> Sorting is a fundamental and well studied problem that has been studied extensively. Sorting plays an important role in the area of databases, as many queries can be served much faster if the relations are first sorted. One of the most popular sorting algorithm in databases is merge sort. In modern data-centers, data is stored in storage servers, while processing takes place in compute servers.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.14071v1-abstract-full').style.display = 'inline'; document.getElementById('2103.14071v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2103.14071v1-abstract-full" style="display: none;"> Sorting is a fundamental and well studied problem that has been studied extensively. Sorting plays an important role in the area of databases, as many queries can be served much faster if the relations are first sorted. One of the most popular sorting algorithm in databases is merge sort. In modern data-centers, data is stored in storage servers, while processing takes place in compute servers. Hence, in order to compute queries on the data, it must travel through the network from the storage servers to the compute servers. This creates a potential for utilizing programmable switches to perform partial sorting in order to accelerate the sorting process at the server side. This is possible because, as mentioned above, data packets pass through the switch in any case on their way to the server. Alas, programmable switches offer a very restricted and non-intuitive programming model, which is why realizing this is not-trivial. We devised a novel partial sorting algorithm that fits the programming model and restrictions of programmable switches and can expedite merge sort at the server. We also utilize built-in parallelism in the switch to divide the data into sequential ranges. Thus, the server needs to sort each range separately and then concatenate them to one sorted stream. This way, the server needs to sort smaller sections and each of these sections is already partially sorted. Hence, the server does less work, and the access pattern becomes more virtual-memory friendly. We evaluated the performance improvements obtained when utilizing our partial sorting algorithm over several data stream compositions with various switch configurations. Our study exhibits an improvement of 20%-75% in the sorting run-time when using our approach compared to plain sorting on the original stream. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2103.14071v1-abstract-full').style.display = 'none'; document.getElementById('2103.14071v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 25 March, 2021; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2021. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2010.14189">arXiv:2010.14189</a> <span> [<a href="https://arxiv.org/pdf/2010.14189">pdf</a>, <a href="https://arxiv.org/format/2010.14189">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Databases">cs.DB</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Jiffy: A Fast, Memory Efficient, Wait-Free Multi-Producers Single-Consumer Queue </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Adas%2C+D">Dolev Adas</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2010.14189v2-abstract-short" style="display: inline;"> In applications such as sharded data processing systems, sharded in-memory key-value stores, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. For scalability, wait-free queues are often prefe… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.14189v2-abstract-full').style.display = 'inline'; document.getElementById('2010.14189v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.14189v2-abstract-full" style="display: none;"> In applications such as sharded data processing systems, sharded in-memory key-value stores, data flow programming and load sharing applications, multiple concurrent data producers are feeding requests into the same data consumer. This can be naturally realized through concurrent queues, where each consumer pulls its tasks from its dedicated queue. For scalability, wait-free queues are often preferred over lock based structures. The vast majority of wait-free queue implementations, and even lock-free ones, support the multi-producer multi-consumer model. Yet, this comes at a premium, since implementing wait-free multi-producer multi-consumer queues requires utilizing complex helper data structures. The latter increases the memory consumption of such queues and limits their performance and scalability. Additionally, many such designs employ (hardware) cache unfriendly memory access patterns. In this work we study the implementation of wait-free multi-producer single-consumer queues. Specifically, we propose Jiffy, an efficient memory frugal novel wait-free multi-producer single-consumer queue and formally prove its correctness. We then compare the performance and memory requirements of Jiffy with other state of the art lock-free and wait-free queues. We show that indeed Jiffy can maintain good performance with up to 128 threads, delivers up to 50% better throughput than the next best construction we compared against, and consumes ~90% less memory. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.14189v2-abstract-full').style.display = 'none'; document.getElementById('2010.14189v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 2 November, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 27 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2010.05369">arXiv:2010.05369</a> <span> [<a href="https://arxiv.org/pdf/2010.05369">pdf</a>, <a href="https://arxiv.org/format/2010.05369">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Quantitative Argument Summarization and Beyond: Cross-Domain Key Point Analysis </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bar-Haim%2C+R">Roy Bar-Haim</a>, <a href="/search/cs?searchtype=author&query=Kantor%2C+Y">Yoav Kantor</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+L">Lilach Eden</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Lahav%2C+D">Dan Lahav</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2010.05369v1-abstract-short" style="display: inline;"> When summarizing a collection of views, arguments or opinions on some topic, it is often desirable not only to extract the most salient points, but also to quantify their prevalence. Work on multi-document summarization has traditionally focused on creating textual summaries, which lack this quantitative aspect. Recent work has proposed to summarize arguments by mapping them to a small set of expe… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.05369v1-abstract-full').style.display = 'inline'; document.getElementById('2010.05369v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2010.05369v1-abstract-full" style="display: none;"> When summarizing a collection of views, arguments or opinions on some topic, it is often desirable not only to extract the most salient points, but also to quantify their prevalence. Work on multi-document summarization has traditionally focused on creating textual summaries, which lack this quantitative aspect. Recent work has proposed to summarize arguments by mapping them to a small set of expert-generated key points, where the salience of each key point corresponds to the number of its matching arguments. The current work advances key point analysis in two important respects: first, we develop a method for automatic extraction of key points, which enables fully automatic analysis, and is shown to achieve performance comparable to a human expert. Second, we demonstrate that the applicability of key point analysis goes well beyond argumentation data. Using models trained on publicly available argumentation datasets, we achieve promising results in two additional domains: municipal surveys and user reviews. An additional contribution is an in-depth evaluation of argument-to-key point matching models, where we substantially outperform previous results. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2010.05369v1-abstract-full').style.display = 'none'; document.getElementById('2010.05369v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 11 October, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">EMNLP 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/2005.01619">arXiv:2005.01619</a> <span> [<a href="https://arxiv.org/pdf/2005.01619">pdf</a>, <a href="https://arxiv.org/format/2005.01619">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> From Arguments to Key Points: Towards Automatic Argument Summarization </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Bar-Haim%2C+R">Roy Bar-Haim</a>, <a href="/search/cs?searchtype=author&query=Eden%2C+L">Lilach Eden</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Kantor%2C+Y">Yoav Kantor</a>, <a href="/search/cs?searchtype=author&query=Lahav%2C+D">Dan Lahav</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="2005.01619v2-abstract-short" style="display: inline;"> Generating a concise summary from a large collection of arguments on a given topic is an intriguing yet understudied problem. We propose to represent such summaries as a small set of talking points, termed "key points", each scored according to its salience. We show, by analyzing a large dataset of crowd-contributed arguments, that a small number of key points per topic is typically sufficient for… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2005.01619v2-abstract-full').style.display = 'inline'; document.getElementById('2005.01619v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="2005.01619v2-abstract-full" style="display: none;"> Generating a concise summary from a large collection of arguments on a given topic is an intriguing yet understudied problem. We propose to represent such summaries as a small set of talking points, termed "key points", each scored according to its salience. We show, by analyzing a large dataset of crowd-contributed arguments, that a small number of key points per topic is typically sufficient for covering the vast majority of the arguments. Furthermore, we found that a domain expert can often predict these key points in advance. We study the task of argument-to-key point mapping, and introduce a novel large-scale dataset for this task. We report empirical results for an extensive set of experiments with this dataset, showing promising performance. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('2005.01619v2-abstract-full').style.display = 'none'; document.getElementById('2005.01619v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 June, 2020; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 4 May, 2020; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2020. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">ACL 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1911.11408">arXiv:1911.11408</a> <span> [<a href="https://arxiv.org/pdf/1911.11408">pdf</a>, <a href="https://arxiv.org/format/1911.11408">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> A Large-scale Dataset for Argument Quality Ranking: Construction and Analysis </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Gretz%2C+S">Shai Gretz</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Cohen-Karlik%2C+E">Edo Cohen-Karlik</a>, <a href="/search/cs?searchtype=author&query=Toledo%2C+A">Assaf Toledo</a>, <a href="/search/cs?searchtype=author&query=Lahav%2C+D">Dan Lahav</a>, <a href="/search/cs?searchtype=author&query=Aharonov%2C+R">Ranit Aharonov</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1911.11408v1-abstract-short" style="display: inline;"> Identifying the quality of free-text arguments has become an important task in the rapidly expanding field of computational argumentation. In this work, we explore the challenging task of argument quality ranking. To this end, we created a corpus of 30,497 arguments carefully annotated for point-wise quality, released as part of this work. To the best of our knowledge, this is the largest dataset… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1911.11408v1-abstract-full').style.display = 'inline'; document.getElementById('1911.11408v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1911.11408v1-abstract-full" style="display: none;"> Identifying the quality of free-text arguments has become an important task in the rapidly expanding field of computational argumentation. In this work, we explore the challenging task of argument quality ranking. To this end, we created a corpus of 30,497 arguments carefully annotated for point-wise quality, released as part of this work. To the best of our knowledge, this is the largest dataset annotated for point-wise argument quality, larger by a factor of five than previously released datasets. Moreover, we address the core issue of inducing a labeled score from crowd annotations by performing a comprehensive evaluation of different approaches to this problem. In addition, we analyze the quality dimensions that characterize this dataset. Finally, we present a neural method for argument quality ranking, which outperforms several baselines on our own dataset, as well as previous methods published for another dataset. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1911.11408v1-abstract-full').style.display = 'none'; document.getElementById('1911.11408v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 26 November, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to AAAI 2020</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1909.01007">arXiv:1909.01007</a> <span> [<a href="https://arxiv.org/pdf/1909.01007">pdf</a>, <a href="https://arxiv.org/format/1909.01007">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Computation and Language">cs.CL</span> </div> </div> <p class="title is-5 mathjax"> Automatic Argument Quality Assessment -- New Datasets and Methods </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Toledo%2C+A">Assaf Toledo</a>, <a href="/search/cs?searchtype=author&query=Gretz%2C+S">Shai Gretz</a>, <a href="/search/cs?searchtype=author&query=Cohen-Karlik%2C+E">Edo Cohen-Karlik</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roni Friedman</a>, <a href="/search/cs?searchtype=author&query=Venezian%2C+E">Elad Venezian</a>, <a href="/search/cs?searchtype=author&query=Lahav%2C+D">Dan Lahav</a>, <a href="/search/cs?searchtype=author&query=Jacovi%2C+M">Michal Jacovi</a>, <a href="/search/cs?searchtype=author&query=Aharonov%2C+R">Ranit Aharonov</a>, <a href="/search/cs?searchtype=author&query=Slonim%2C+N">Noam Slonim</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1909.01007v1-abstract-short" style="display: inline;"> We explore the task of automatic assessment of argument quality. To that end, we actively collected 6.3k arguments, more than a factor of five compared to previously examined data. Each argument was explicitly and carefully annotated for its quality. In addition, 14k pairs of arguments were annotated independently, identifying the higher quality argument in each pair. In spite of the inherent subj… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1909.01007v1-abstract-full').style.display = 'inline'; document.getElementById('1909.01007v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1909.01007v1-abstract-full" style="display: none;"> We explore the task of automatic assessment of argument quality. To that end, we actively collected 6.3k arguments, more than a factor of five compared to previously examined data. Each argument was explicitly and carefully annotated for its quality. In addition, 14k pairs of arguments were annotated independently, identifying the higher quality argument in each pair. In spite of the inherent subjective nature of the task, both annotation schemes led to surprisingly consistent results. We release the labeled datasets to the community. Furthermore, we suggest neural methods based on a recently released language model, for argument ranking as well as for argument-pair classification. In the former task, our results are comparable to state-of-the-art; in the latter task our results significantly outperform earlier methods. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1909.01007v1-abstract-full').style.display = 'none'; document.getElementById('1909.01007v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 September, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> September 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Published at EMNLP 2019</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1908.02675">arXiv:1908.02675</a> <span> [<a href="https://arxiv.org/pdf/1908.02675">pdf</a>, <a href="https://arxiv.org/format/1908.02675">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> A Generic Efficient Biased Optimizer for Consensus Protocols </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Buchnik%2C+Y">Yehonatan Buchnik</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1908.02675v1-abstract-short" style="display: inline;"> Consensus is one of the most fundamental distributed computing problems. In particular, it serves as a building block in many replication based fault-tolerant systems and in particular in multiple recent blockchain solutions. Depending on its exact variant and other environmental assumptions, solving consensus requires multiple communication rounds. Yet, there are known optimistic protocols that g… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1908.02675v1-abstract-full').style.display = 'inline'; document.getElementById('1908.02675v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1908.02675v1-abstract-full" style="display: none;"> Consensus is one of the most fundamental distributed computing problems. In particular, it serves as a building block in many replication based fault-tolerant systems and in particular in multiple recent blockchain solutions. Depending on its exact variant and other environmental assumptions, solving consensus requires multiple communication rounds. Yet, there are known optimistic protocols that guarantee termination in a single communication round under favorable conditions. In this paper we present a generic optimizer than can turn any consensus protocol into an optimized protocol that terminates in a single communication round whenever all nodes start with the same predetermined value and no Byzantine failures occur (although node crashes are allowed). This is regardless of the network timing assumptions and additional oracle capabilities assumed by the base consensus protocol being optimized. In the case of benign failures, our optimizer works whenever the number of faulty nodes $f<n/2$. For Byzantine behavior, our optimizer's resiliency depends on the validity variant sought. In the case of classical validity, it can accommodate $f<n/4$ Byzantine failures. With the more recent external validity function assumption, it works whenever $f<n/3$. Either way, our optimizer only relies on oral messages, thereby imposing very light-weight crypto requirements. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1908.02675v1-abstract-full').style.display = 'none'; document.getElementById('1908.02675v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 7 August, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> August 2019. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1901.03279">arXiv:1901.03279</a> <span> [<a href="https://arxiv.org/pdf/1901.03279">pdf</a>, <a href="https://arxiv.org/format/1901.03279">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> FireLedger: A High Throughput Blockchain Consensus Protocol </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Buchnik%2C+Y">Yehonatan Buchnik</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1901.03279v6-abstract-short" style="display: inline;"> Blockchains are distributed secure ledgers to which transactions are issued continuously and each block of transactions is tightly coupled to its predecessors. Permissioned blockchains place special emphasis on transactions throughput. In this paper we present FireLedger, which leverages the iterative nature of blockchains in order to improve their throughput in optimistic execution scenarios. Fir… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.03279v6-abstract-full').style.display = 'inline'; document.getElementById('1901.03279v6-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1901.03279v6-abstract-full" style="display: none;"> Blockchains are distributed secure ledgers to which transactions are issued continuously and each block of transactions is tightly coupled to its predecessors. Permissioned blockchains place special emphasis on transactions throughput. In this paper we present FireLedger, which leverages the iterative nature of blockchains in order to improve their throughput in optimistic execution scenarios. FireLedger trades latency for throughput in the sense that in FireLedger the last f + 1 blocks of each node's blockchain are considered tentative, i.e., they may be rescinded in case one of the last f + 1 blocks proposers was Byzantine. Yet, when optimistic assumptions are met, a new block is decided in each communication step, which consists of a proposer that sends only its proposal and all other participants are sending a single bit each. Our performance study demonstrates that in a single Amazon data-center, FireLedger running on 10 mid-range Amazon nodes obtains a throughput of up to 160K transactions per second for (typical Bitcoin size) 512 bytes transactions. In a 10 nodes Amazon geo-distributed setting with 512 bytes transactions, FireLedger obtains a throughput of 30K tps. Moreover, on higher end Amazon machines, FireLedger obtains $20%-600%$ better throughput than state of the art protocols like HotStuff and BFT-SMaRt, depending on the exact configuration. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1901.03279v6-abstract-full').style.display = 'none'; document.getElementById('1901.03279v6-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 1 November, 2019; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 10 January, 2019; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2019. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">The name of the protocol was changed from TOY to FireLedger. Protocol presentation and related work sections were improved and some typos were fixed</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1804.10740">arXiv:1804.10740</a> <span> [<a href="https://arxiv.org/pdf/1804.10740">pdf</a>, <a href="https://arxiv.org/format/1804.10740">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Heavy Hitters over Interval Queries </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Shahout%2C+R">Rana Shahout</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1804.10740v2-abstract-short" style="display: inline;"> Heavy hitters and frequency measurements are fundamental in many networking applications such as load balancing, QoS, and network security. This paper considers a generalized sliding window model that supports frequency and heavy hitters queries over an interval given at \emph{query time}. This enables drill-down queries, in which the behavior of the network can be examined in finer and finer gran… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.10740v2-abstract-full').style.display = 'inline'; document.getElementById('1804.10740v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1804.10740v2-abstract-full" style="display: none;"> Heavy hitters and frequency measurements are fundamental in many networking applications such as load balancing, QoS, and network security. This paper considers a generalized sliding window model that supports frequency and heavy hitters queries over an interval given at \emph{query time}. This enables drill-down queries, in which the behavior of the network can be examined in finer and finer granularities. For this model, we asymptotically improve the space bounds of existing work, reduce the update and query time to a constant, and provide deterministic solutions. When evaluated over real Internet packet traces, our fastest algorithm processes packets $90$--$250$ times faster, serves queries at least $730$ times quicker and consumes at least $40\%$ less space than the known method. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1804.10740v2-abstract-full').style.display = 'none'; document.getElementById('1804.10740v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 13 November, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 28 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2018. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1712.01779">arXiv:1712.01779</a> <span> [<a href="https://arxiv.org/pdf/1712.01779">pdf</a>, <a href="https://arxiv.org/format/1712.01779">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Pay for a Sliding Bloom Filter and Get Counting, Distinct Elements, and Entropy for Free </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Assaf%2C+E">Eran Assaf</a>, <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1712.01779v1-abstract-short" style="display: inline;"> For many networking applications, recent data is more significant than older data, motivating the need for sliding window solutions. Various capabilities, such as DDoS detection and load balancing, require insights about multiple metrics including Bloom filters, per-flow counting, count distinct and entropy estimation. In this work, we present a unified construction that solves all the above pro… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1712.01779v1-abstract-full').style.display = 'inline'; document.getElementById('1712.01779v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1712.01779v1-abstract-full" style="display: none;"> For many networking applications, recent data is more significant than older data, motivating the need for sliding window solutions. Various capabilities, such as DDoS detection and load balancing, require insights about multiple metrics including Bloom filters, per-flow counting, count distinct and entropy estimation. In this work, we present a unified construction that solves all the above problems in the sliding window model. Our single solution offers a better space to accuracy tradeoff than the state-of-the-art for each of these individual problems! We show this both analytically and by running multiple real Internet backbone and datacenter packet traces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1712.01779v1-abstract-full').style.display = 'none'; document.getElementById('1712.01779v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 5 December, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in IEEE INFOCOM 2018</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1710.03155">arXiv:1710.03155</a> <span> [<a href="https://arxiv.org/pdf/1710.03155">pdf</a>, <a href="https://arxiv.org/format/1710.03155">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Fast Flow Volume Estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1710.03155v3-abstract-short" style="display: inline;"> The increasing popularity of jumbo frames means growing variance in the size of packets transmitted in modern networks. Consequently, network monitoring tools must maintain explicit traffic volume statistics rather than settle for packet counting as before. We present constant time algorithms for volume estimations in streams and sliding windows, which are faster than previous work. Our solutions… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.03155v3-abstract-full').style.display = 'inline'; document.getElementById('1710.03155v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1710.03155v3-abstract-full" style="display: none;"> The increasing popularity of jumbo frames means growing variance in the size of packets transmitted in modern networks. Consequently, network monitoring tools must maintain explicit traffic volume statistics rather than settle for packet counting as before. We present constant time algorithms for volume estimations in streams and sliding windows, which are faster than previous work. Our solutions are formally analyzed and are extensively evaluated over multiple real-world packet traces as well as synthetic ones. For streams, we demonstrate a run-time improvement of up to 2.4X compared to the state of the art. On sliding windows, we exhibit a memory reduction of over 100X on all traces and an asymptotic runtime improvement to a constant. Finally, we apply our approach to hierarchical heavy hitters and achieve an empirical 2.4-7X speedup. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1710.03155v3-abstract-full').style.display = 'none'; document.getElementById('1710.03155v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 October, 2017; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 9 October, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in ACM ICDCN 2018</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1707.06778">arXiv:1707.06778</a> <span> [<a href="https://arxiv.org/pdf/1707.06778">pdf</a>, <a href="https://arxiv.org/format/1707.06778">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1145/3098822.3098832">10.1145/3098822.3098832 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Constant Time Updates in Hierarchical Heavy Hitters </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Luizelli%2C+M+C">Marcelo Caggiani Luizelli</a>, <a href="/search/cs?searchtype=author&query=Waisbard%2C+E">Erez Waisbard</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1707.06778v1-abstract-short" style="display: inline;"> Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as \emph{hierarchical heavy hitters} (HHH), where the hierarchy is determined based on the type of prefixes of interest in a given application. The per packet complexity of existing HHH algorithms is proportional to the size of the hierarchy, imposing sign… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1707.06778v1-abstract-full').style.display = 'inline'; document.getElementById('1707.06778v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1707.06778v1-abstract-full" style="display: none;"> Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as \emph{hierarchical heavy hitters} (HHH), where the hierarchy is determined based on the type of prefixes of interest in a given application. The per packet complexity of existing HHH algorithms is proportional to the size of the hierarchy, imposing significant overheads. In this paper, we propose a randomized constant time algorithm for HHH. We prove probabilistic precision bounds backed by an empirical evaluation. Using four real Internet packet traces, we demonstrate that our algorithm indeed obtains comparable accuracy and recall as previous works, while running up to 62 times faster. Finally, we extended Open vSwitch (OVS) with our algorithm and showed it is able to handle 13.8 million packets per second. In contrast, incorporating previous works in OVS only obtained 2.5 times lower throughput. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1707.06778v1-abstract-full').style.display = 'none'; document.getElementById('1707.06778v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 21 July, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">To appear in ACM SIGCOMM 2017</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1703.01166">arXiv:1703.01166</a> <span> [<a href="https://arxiv.org/pdf/1703.01166">pdf</a>, <a href="https://arxiv.org/format/1703.01166">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Give Me Some Slack: Efficient Network Measurements </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1703.01166v3-abstract-short" style="display: inline;"> Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing \emph{slack} in the window size on the asymptotic requirements of sliding window problems. That is,… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1703.01166v3-abstract-full').style.display = 'inline'; document.getElementById('1703.01166v3-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1703.01166v3-abstract-full" style="display: none;"> Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing \emph{slack} in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between $W$ and $W(1+蟿)$ where $蟿$ is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as MAX and GENERAL-SUM that require $惟(W)$ bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as BASIC-SUMMING and COUNT-DISTINCT, the slack model enables a further asymptotic improvement. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1703.01166v3-abstract-full').style.display = 'none'; document.getElementById('1703.01166v3-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 24 April, 2018; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 3 March, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> March 2017. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1701.04021">arXiv:1701.04021</a> <span> [<a href="https://arxiv.org/pdf/1701.04021">pdf</a>, <a href="https://arxiv.org/format/1701.04021">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> </div> <p class="title is-5 mathjax"> Optimal Elephant Flow Detection </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Kassner%2C+Y">Yaron Kassner</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1701.04021v1-abstract-short" style="display: inline;"> Monitoring the traffic volumes of elephant flows, including the total byte count per flow, is a fundamental capability for online network measurements. We present an asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves on previous approaches, which can only count the number of packets in constant time. We evaluate our work on real pack… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.04021v1-abstract-full').style.display = 'inline'; document.getElementById('1701.04021v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1701.04021v1-abstract-full" style="display: none;"> Monitoring the traffic volumes of elephant flows, including the total byte count per flow, is a fundamental capability for online network measurements. We present an asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves on previous approaches, which can only count the number of packets in constant time. We evaluate our work on real packet traces, demonstrating an up to X2.5 speedup compared to the best alternative. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1701.04021v1-abstract-full').style.display = 'none'; document.getElementById('1701.04021v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 15 January, 2017; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> January 2017. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Accepted to IEEE INFOCOM 2017</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1612.02962">arXiv:1612.02962</a> <span> [<a href="https://arxiv.org/pdf/1612.02962">pdf</a>, <a href="https://arxiv.org/format/1612.02962">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> Randomized Admission Policy for Efficient Top-k and Frequency Estimation </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Kassner%2C+Y">Yaron Kassner</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1612.02962v1-abstract-short" style="display: inline;"> Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) - a novel algorithm for the frequency and top-k estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives by a factor of up to 32 on real packet traces and up to 128 on h… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1612.02962v1-abstract-full').style.display = 'inline'; document.getElementById('1612.02962v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1612.02962v1-abstract-full" style="display: none;"> Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) - a novel algorithm for the frequency and top-k estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the skew of the workload. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. Additionally, we present d-Way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1612.02962v1-abstract-full').style.display = 'none'; document.getElementById('1612.02962v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 9 December, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">Conference version accepted to IEEE INFOCOM2017</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1610.02885">arXiv:1610.02885</a> <span> [<a href="https://arxiv.org/pdf/1610.02885">pdf</a>, <a href="https://arxiv.org/format/1610.02885">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> Hardening Cassandra Against Byzantine Failures </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Licher%2C+R">Roni Licher</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1610.02885v1-abstract-short" style="display: inline;"> Cassandra is one of the most widely used distributed data stores these days. Cassandra supports flexible consistency guarantees over a wide-column data access model and provides almost linear scale-out performance. This enables application developers to tailor the performance and availability of Cassandra to their exact application's needs and required semantics. Yet, Cassandra is designed to with… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1610.02885v1-abstract-full').style.display = 'inline'; document.getElementById('1610.02885v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1610.02885v1-abstract-full" style="display: none;"> Cassandra is one of the most widely used distributed data stores these days. Cassandra supports flexible consistency guarantees over a wide-column data access model and provides almost linear scale-out performance. This enables application developers to tailor the performance and availability of Cassandra to their exact application's needs and required semantics. Yet, Cassandra is designed to withstand benign failures, and cannot cope with most forms of Byzantine attacks. In this work, we present an analysis of Cassandra's vulnerabilities and propose protocols for hardening Cassandra against Byzantine failures. We examine several alternative design choices and compare between them both qualitatively and empirically by using the Yahoo! Cloud Serving Benchmark (YCSB) performance benchmark. We include incremental performance analysis for our algorithmic and cryptographic adjustments, supporting our design choices. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1610.02885v1-abstract-full').style.display = 'none'; document.getElementById('1610.02885v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 10 October, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> October 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1606.01364">arXiv:1606.01364</a> <span> [<a href="https://arxiv.org/pdf/1606.01364">pdf</a>, <a href="https://arxiv.org/format/1606.01364">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> ICE Buckets: Improved Counter Estimation for Network Measurement </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Fellman%2C+B">Benny Fellman</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Kassner%2C+Y">Yaron Kassner</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1606.01364v1-abstract-short" style="display: inline;"> Measurement capabilities are essential for a variety of network applications, such as load balancing, routing, fairness and intrusion detection. These capabilities require large counter arrays in order to monitor the traffic of all network flows. While commodity SRAM memories are capable of operating at line speed, they are too small to accommodate large counter arrays. Previous works suggested es… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1606.01364v1-abstract-full').style.display = 'inline'; document.getElementById('1606.01364v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1606.01364v1-abstract-full" style="display: none;"> Measurement capabilities are essential for a variety of network applications, such as load balancing, routing, fairness and intrusion detection. These capabilities require large counter arrays in order to monitor the traffic of all network flows. While commodity SRAM memories are capable of operating at line speed, they are too small to accommodate large counter arrays. Previous works suggested estimators, which trade precision for reduced space. However, in order to accurately estimate the largest counter, these methods compromise the accuracy of the smaller counters. In this work, we present a closed form representation of the optimal estimation function. We then introduce Independent Counter Estimation Buckets (ICE-Buckets), a novel algorithm that improves estimation accuracy for all counters. This is achieved by separating the flows to buckets and configuring the optimal estimation function according to each bucket's counter scale. We prove a tighter upper bound on the relative error and demonstrate an accuracy improvement of up to 57 times on real Internet packet traces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1606.01364v1-abstract-full').style.display = 'none'; document.getElementById('1606.01364v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 4 June, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> June 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1604.02450">arXiv:1604.02450</a> <span> [<a href="https://arxiv.org/pdf/1604.02450">pdf</a>, <a href="https://arxiv.org/format/1604.02450">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Data Structures and Algorithms">cs.DS</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.4230/LIPIcs.SWAT.2016">10.4230/LIPIcs.SWAT.2016 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Efficient Summing over Sliding Windows </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Basat%2C+R+B">Ran Ben Basat</a>, <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Kassner%2C+Y">Yaron Kassner</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1604.02450v1-abstract-short" style="display: inline;"> This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of 惟(1/蔚 + log W) memory bits for W蔚-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/蔚 + log W) bits, indicating that t… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.02450v1-abstract-full').style.display = 'inline'; document.getElementById('1604.02450v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1604.02450v1-abstract-full" style="display: none;"> This paper considers the problem of maintaining statistic aggregates over the last W elements of a data stream. First, the problem of counting the number of 1's in the last W bits of a binary stream is considered. A lower bound of 惟(1/蔚 + log W) memory bits for W蔚-additive approximations is derived. This is followed by an algorithm whose memory consumption is O(1/蔚 + log W) bits, indicating that the algorithm is optimal and that the bound is tight. Next, the more general problem of maintaining a sum of the last W integers, each in the range of {0,1,...,R}, is addressed. The paper shows that approximating the sum within an additive error of RW蔚 can also be done using 螛(1/蔚 + log W) bits for 蔚=惟(1/W). For 蔚=o(1/W), we present a succinct algorithm which uses B(1 + o(1)) bits, where B=螛(Wlog(1/W蔚)) is the derived lower bound. We show that all lower bounds generalize to randomized algorithms as well. All algorithms process new elements and answer queries in O(1) worst-case time. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.02450v1-abstract-full').style.display = 'none'; document.getElementById('1604.02450v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 April, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2016. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">A shorter version appears in SWAT 2016</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1604.00641">arXiv:1604.00641</a> <span> [<a href="https://arxiv.org/pdf/1604.00641">pdf</a>, <a href="https://arxiv.org/format/1604.00641">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> COARA: Code Offloading on Android with AspectJ </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Hauser%2C+N">Nir Hauser</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1604.00641v1-abstract-short" style="display: inline;"> Smartphones suffer from limited computational capabilities and battery life. A method to mitigate these problems is code offloading: executing application code on a remote server. We introduce COARA, a middleware platform for code offloading on Android that uses aspect-oriented programming (AOP) with AspectJ. AOP allows COARA to intercept code for offloading without a customized compiler or modifi… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.00641v1-abstract-full').style.display = 'inline'; document.getElementById('1604.00641v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1604.00641v1-abstract-full" style="display: none;"> Smartphones suffer from limited computational capabilities and battery life. A method to mitigate these problems is code offloading: executing application code on a remote server. We introduce COARA, a middleware platform for code offloading on Android that uses aspect-oriented programming (AOP) with AspectJ. AOP allows COARA to intercept code for offloading without a customized compiler or modification of the operating system. COARA requires minimal changes to application source code, and does not require the application developer to be aware of AOP. Since state transfer to the server is often a bottleneck that hinders performance, COARA uses AOP to intercept the transmission of large objects from the client and replaces them with object proxies. The server can begin execution of the offloaded application code, regardless of whether all required objects been transferred to the server. We run COARA with Android applications from the Google Play store on a Nexus 4 running unmodified Android 4.3 to prove that our platform improves performance and reduces energy consumption. Our approach yields speedups of 24x and 6x over WiFi and 3G respectively. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1604.00641v1-abstract-full').style.display = 'none'; document.getElementById('1604.00641v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 April, 2016; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> April 2016. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1512.00727">arXiv:1512.00727</a> <span> [<a href="https://arxiv.org/pdf/1512.00727">pdf</a>, <a href="https://arxiv.org/format/1512.00727">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Operating Systems">cs.OS</span> </div> </div> <p class="title is-5 mathjax"> TinyLFU: A Highly Efficient Cache Admission Policy </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Einziger%2C+G">Gil Einziger</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Manes%2C+B">Ben Manes</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1512.00727v2-abstract-short" style="display: inline;"> This paper proposes to use a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. Realizing this con… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.00727v2-abstract-full').style.display = 'inline'; document.getElementById('1512.00727v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1512.00727v2-abstract-full" style="display: none;"> This paper proposes to use a frequency based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. Realizing this concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and light-weight as it builds upon Bloom filter theory. We study the properties of TinyLFU through simulations of both synthetic workloads as well as multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU eviction policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit-ratios than other state of the art replacement policies on these traces. It is the only scheme to obtain such good results on all traces. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1512.00727v2-abstract-full').style.display = 'none'; document.getElementById('1512.00727v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 3 December, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 2 December, 2015; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> December 2015. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">A much earlier and shorter version of this work appeared in the Euromicro PDP 2014 conference</span> </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/1411.6478">arXiv:1411.6478</a> <span> [<a href="https://arxiv.org/pdf/1411.6478">pdf</a>, <a href="https://arxiv.org/format/1411.6478">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Distributed, Parallel, and Cluster Computing">cs.DC</span> </div> </div> <p class="title is-5 mathjax"> Fisheye Consistency: Keeping Data in Synch in a Georeplicated World </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+R">Roy Friedman</a>, <a href="/search/cs?searchtype=author&query=Raynal%2C+M">Michel Raynal</a>, <a href="/search/cs?searchtype=author&query=Ta%C3%AFani%2C+F">Fran莽ois Ta茂ani</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="1411.6478v2-abstract-short" style="display: inline;"> Over the last thirty years, numerous consistency conditions for replicated data have been proposed and implemented. Popular examples of such conditions include linearizability (or atomicity), sequential consistency, causal consistency, and eventual consistency. These consistency conditions are usually defined independently from the computing entities (nodes) that manipulate the replicated data; i.… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1411.6478v2-abstract-full').style.display = 'inline'; document.getElementById('1411.6478v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="1411.6478v2-abstract-full" style="display: none;"> Over the last thirty years, numerous consistency conditions for replicated data have been proposed and implemented. Popular examples of such conditions include linearizability (or atomicity), sequential consistency, causal consistency, and eventual consistency. These consistency conditions are usually defined independently from the computing entities (nodes) that manipulate the replicated data; i.e., they do not take into account how computing entities might be linked to one another, or geographically distributed. To address this lack, as a first contribution, this paper introduces the notion of proximity graph between computing nodes. If two nodes are connected in this graph, their operations must satisfy a strong consistency condition, while the operations invoked by other nodes are allowed to satisfy a weaker condition. The second contribution is the use of such a graph to provide a generic approach to the hybridization of data consistency conditions into the same system. We illustrate this approach on sequential consistency and causal consistency, and present a model in which all data operations are causally consistent, while operations by neighboring processes in the proximity graph are sequentially consistent. The third contribution of the paper is the design and the proof of a distributed algorithm based on this proximity graph, which combines sequential consistency and causal consistency (the resulting condition is called fisheye consistency). In doing so the paper not only extends the domain of consistency conditions, but provides a generic provably correct solution of direct relevance to modern georeplicated systems. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('1411.6478v2-abstract-full').style.display = 'none'; document.getElementById('1411.6478v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 22 October, 2015; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 24 November, 2014; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> November 2014. </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/0807.1253">arXiv:0807.1253</a> <span> [<a href="https://arxiv.org/pdf/0807.1253">pdf</a>, <a href="https://arxiv.org/ps/0807.1253">ps</a>, <a href="https://arxiv.org/format/0807.1253">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Trading and Market Microstructure">q-fin.TR</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Information Theory">cs.IT</span> <span class="tag is-small is-grey tooltip is-tooltip-top" data-tooltip="Probability">math.PR</span> </div> <div class="is-inline-block" style="margin-left: 0.5rem"> <div class="tags has-addons"> <span class="tag is-dark is-size-7">doi</span> <span class="tag is-light is-size-7"><a class="" href="https://doi.org/10.1098/rspa.2008.0465">10.1098/rspa.2008.0465 <i class="fa fa-external-link" aria-hidden="true"></i></a></span> </div> </div> </div> <p class="title is-5 mathjax"> Informed Traders </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Brody%2C+D+C">Dorje C. Brody</a>, <a href="/search/cs?searchtype=author&query=Davis%2C+M+H+A">Mark H. A. Davis</a>, <a href="/search/cs?searchtype=author&query=Friedman%2C+R+L">Robyn L. Friedman</a>, <a href="/search/cs?searchtype=author&query=Hughston%2C+L+P">Lane P. Hughston</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="0807.1253v2-abstract-short" style="display: inline;"> An asymmetric information model is introduced for the situation in which there is a small agent who is more susceptible to the flow of information in the market than the general market participant, and who tries to implement strategies based on the additional information. In this model market participants have access to a stream of noisy information concerning the future return of an asset, wher… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0807.1253v2-abstract-full').style.display = 'inline'; document.getElementById('0807.1253v2-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="0807.1253v2-abstract-full" style="display: none;"> An asymmetric information model is introduced for the situation in which there is a small agent who is more susceptible to the flow of information in the market than the general market participant, and who tries to implement strategies based on the additional information. In this model market participants have access to a stream of noisy information concerning the future return of an asset, whereas the informed trader has access to a further information source which is obscured by an additional noise that may be correlated with the market noise. The informed trader uses the extraneous information source to seek statistical arbitrage opportunities, while at the same time accommodating the additional risk. The amount of information available to the general market participant concerning the asset return is measured by the mutual information of the asset price and the associated cash flow. The worth of the additional information source is then measured in terms of the difference of mutual information between the general market participant and the informed trader. This difference is shown to be nonnegative when the signal-to-noise ratio of the information flow is known in advance. Explicit trading strategies leading to statistical arbitrage opportunities, taking advantage of the additional information, are constructed, illustrating how excess information can be translated into profit. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('0807.1253v2-abstract-full').style.display = 'none'; document.getElementById('0807.1253v2-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 17 November, 2008; <span class="has-text-black-bis has-text-weight-semibold">v1</span> submitted 8 July, 2008; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> July 2008. </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Comments:</span> <span class="has-text-grey-dark mathjax">20 pages, 5 figures. Version to appear in the Proceedings of the Royal Society A</span> </p> <p class="comments is-size-7"> <span class="has-text-black-bis has-text-weight-semibold">Journal ref:</span> Proceedings of the Royal Society London A465, 1103-1122 (2009) </p> </li> <li class="arxiv-result"> <div class="is-marginless"> <p class="list-title is-inline-block"><a href="https://arxiv.org/abs/cs/0605133">arXiv:cs/0605133</a> <span> [<a href="https://arxiv.org/pdf/cs/0605133">pdf</a>, <a href="https://arxiv.org/ps/cs/0605133">ps</a>, <a href="https://arxiv.org/format/cs/0605133">other</a>] </span> </p> <div class="tags is-inline-block"> <span class="tag is-small is-link tooltip is-tooltip-top" data-tooltip="Networking and Internet Architecture">cs.NI</span> </div> </div> <p class="title is-5 mathjax"> Efficient Route Tracing from a Single Source </p> <p class="authors"> <span class="search-hit">Authors:</span> <a href="/search/cs?searchtype=author&query=Friedman%2C+B+D+P+R+T">Benoit Donnet Philippe Raoult Timur Friedman</a> </p> <p class="abstract mathjax"> <span class="has-text-black-bis has-text-weight-semibold">Abstract</span>: <span class="abstract-short has-text-grey-dark mathjax" id="cs/0605133v1-abstract-short" style="display: inline;"> Traceroute is a networking tool that allows one to discover the path that packets take from a source machine, through the network, to a destination machine. It is widely used as an engineering tool, and also as a scientific tool, such as for discovery of the network topology at the IP level. In prior work, authors on this technical report have shown how to improve the efficiency of route tracing… <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0605133v1-abstract-full').style.display = 'inline'; document.getElementById('cs/0605133v1-abstract-short').style.display = 'none';">▽ More</a> </span> <span class="abstract-full has-text-grey-dark mathjax" id="cs/0605133v1-abstract-full" style="display: none;"> Traceroute is a networking tool that allows one to discover the path that packets take from a source machine, through the network, to a destination machine. It is widely used as an engineering tool, and also as a scientific tool, such as for discovery of the network topology at the IP level. In prior work, authors on this technical report have shown how to improve the efficiency of route tracing from multiple cooperating monitors. However, it is not unusual for a route tracing monitor to operate in isolation. Somewhat different strategies are required for this case, and this report is the first systematic study of those requirements. Standard traceroute is inefficient when used repeatedly towards multiple destinations, as it repeatedly probes the same interfaces close to the source. Others have recognized this inefficiency and have proposed tracing backwards from the destinations and stopping probing upon encounter with a previously-seen interface. One of this technical report's contributions is to quantify for the first time the efficiency of this approach. Another contribution is to describe the effect of non-responding destinations on this efficiency. Since a large portion of destination machines do not reply to probe packets, backwards probing from the destination is often infeasible. We propose an algorithm to tackle non-responding destinations, and we find that our algorithm can strongly decrease probing redundancy at the cost of a small reduction in node and link discovery. <a class="is-size-7" style="white-space: nowrap;" onclick="document.getElementById('cs/0605133v1-abstract-full').style.display = 'none'; document.getElementById('cs/0605133v1-abstract-short').style.display = 'inline';">△ Less</a> </span> </p> <p class="is-size-7"><span class="has-text-black-bis has-text-weight-semibold">Submitted</span> 29 May, 2006; <span class="has-text-black-bis has-text-weight-semibold">originally announced</span> May 2006. </p> </li> </ol> <div class="is-hidden-tablet">  <span class="help" style="display: inline-block;"><a href="https://github.com/arXiv/arxiv-search/releases">Search v0.5.6 released 2020-02-24</a>  </span> </div> </div> </main> <footer> <div class="columns is-desktop" role="navigation" aria-label="Secondary">  <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/about">About</a></li> <li><a href="https://info.arxiv.org/help">Help</a></li> </ul> </div> <div class="column"> <ul class="nav-spaced"> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>contact arXiv</title><desc>Click here to contact arXiv</desc><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg> <a href="https://info.arxiv.org/help/contact.html"> Contact</a> </li> <li> <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><title>subscribe to arXiv mailings</title><desc>Click here to subscribe</desc><path d="M476 3.2L12.5 270.6c-18.1 10.4-15.8 35.6 2.2 43.2L121 358.4l287.3-253.2c5.5-4.9 13.3 2.6 8.6 8.3L176 407v80.5c0 23.6 28.5 32.9 42.5 15.8L282 426l124.6 52.2c14.2 6 30.4-2.9 33-18.2l72-432C515 7.8 493.3-6.8 476 3.2z"/></svg> <a href="https://info.arxiv.org/help/subscribe"> Subscribe</a> </li> </ul> </div> </div> </div>   <div class="column"> <div class="columns"> <div class="column"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/license/index.html">Copyright</a></li> <li><a href="https://info.arxiv.org/help/policies/privacy_policy.html">Privacy Policy</a></li> </ul> </div> <div class="column sorry-app-links"> <ul class="nav-spaced"> <li><a href="https://info.arxiv.org/help/web_accessibility.html">Web Accessibility Assistance</a></li> <li> <p class="help"> <a class="a11y-main-link" href="https://status.arxiv.org" target="_blank">arXiv Operational Status <svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 256 512" class="icon filter-dark_grey" role="presentation"><path d="M224.3 273l-136 136c-9.4 9.4-24.6 9.4-33.9 0l-22.6-22.6c-9.4-9.4-9.4-24.6 0-33.9l96.4-96.4-96.4-96.4c-9.4-9.4-9.4-24.6 0-33.9L54.3 103c9.4-9.4 24.6-9.4 33.9 0l136 136c9.5 9.4 9.5 24.6.1 34z"/></svg></a><br> Get status notifications via <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/email/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512" class="icon filter-black" role="presentation"><path d="M502.3 190.8c3.9-3.1 9.7-.2 9.7 4.7V400c0 26.5-21.5 48-48 48H48c-26.5 0-48-21.5-48-48V195.6c0-5 5.7-7.8 9.7-4.7 22.4 17.4 52.1 39.5 154.1 113.6 21.1 15.4 56.7 47.8 92.2 47.6 35.7.3 72-32.8 92.3-47.6 102-74.1 131.6-96.3 154-113.7zM256 320c23.2.4 56.6-29.2 73.4-41.4 132.7-96.3 142.8-104.7 173.4-128.7 5.8-4.5 9.2-11.5 9.2-18.9v-19c0-26.5-21.5-48-48-48H48C21.5 64 0 85.5 0 112v19c0 7.4 3.4 14.3 9.2 18.9 30.6 23.9 40.7 32.4 173.4 128.7 16.8 12.2 50.2 41.8 73.4 41.4z"/></svg>email</a> or <a class="is-link" href="https://subscribe.sorryapp.com/24846f03/slack/new" target="_blank"><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 448 512" class="icon filter-black" role="presentation"><path d="M94.12 315.1c0 25.9-21.16 47.06-47.06 47.06S0 341 0 315.1c0-25.9 21.16-47.06 47.06-47.06h47.06v47.06zm23.72 0c0-25.9 21.16-47.06 47.06-47.06s47.06 21.16 47.06 47.06v117.84c0 25.9-21.16 47.06-47.06 47.06s-47.06-21.16-47.06-47.06V315.1zm47.06-188.98c-25.9 0-47.06-21.16-47.06-47.06S139 32 164.9 32s47.06 21.16 47.06 47.06v47.06H164.9zm0 23.72c25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06H47.06C21.16 243.96 0 222.8 0 196.9s21.16-47.06 47.06-47.06H164.9zm188.98 47.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06s-21.16 47.06-47.06 47.06h-47.06V196.9zm-23.72 0c0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06V79.06c0-25.9 21.16-47.06 47.06-47.06 25.9 0 47.06 21.16 47.06 47.06V196.9zM283.1 385.88c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06-25.9 0-47.06-21.16-47.06-47.06v-47.06h47.06zm0-23.72c-25.9 0-47.06-21.16-47.06-47.06 0-25.9 21.16-47.06 47.06-47.06h117.84c25.9 0 47.06 21.16 47.06 47.06 0 25.9-21.16 47.06-47.06 47.06H283.1z"/></svg>slack</a> </p> </li> </ul> </div> </div> </div>  </div> </footer> <script src="https://static.arxiv.org/static/base/1.0.0a5/js/member_acknowledgement.js"></script> </body> </html>

CINXE.COM

Search | arXiv e-print repository