</noscript> <!-- End Google Tag Manager (noscript) --> <!-- place holder --><div id="header" class="row"> <nav class="top-bar eyebrow show-for-medium-up" data-topbar data-options="is_hover: false"> <section class="top-bar-section"> <div id="skiptocontent"><a href="#SkipTarget">skip to main content</a></div> <ul class="right"> <li><a href="http://www.acm.org" title="ACM Home">ACM Home</a></li> <li><a href="http://amturing.acm.org/" title="ACM A.M. Turing Award">ACM A.M. Turing Award</a></li> <li><a href="http://queue.acm.org" title="Queue">Queue</a></li> <li><a href="http://dl.acm.org" title="Digital Library">Digital Library</a></li> <li><a href="https://learning.acm.org" title="Learning Center">Learning Center</a></li> <li><a href="https://jobs.acm.org" title="Career Center">Career Center</a></li> </ul> </section> </nav> <div class="clearfix utilities-area"> <div class="logo-section"> <div class="navbar-header show-for-large-up"> <a class="navbar-brand" href="https://www.acm.org"> <img alt="ACM Logo" class="img-responsive" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_tablet.svg"> </a> </div> <div class="navbar-header hide-for-large-up"> <a href="/"> <img alt="ACM Logo" class="img-responsive hide-for-large-up" title="Home" src="/binaries/content/gallery/global/top-menu/acm_logo_mobile.svg"> </a> </div> </div> <div id="acm-description" class="column large-5 show-for-large-up"> <div> Advancing Computing as a Science & Profession<!-- We're an international society of educators, scientists, technologists and engineers dedicated to the advancement of computer science. We offer a world-class <a href="#">Digital Library</a>, <a href="#">publications</a>, <a href="#">conferences</a>, and more. --> </div> </div> <div id="ctas-and-search" class="column large-5 medium-6 no-pad-left ctas-and-search"> <ul class="block-grid right"> <li><a href="http://www.acm.org/membership/join">Join</a></li> <li><a href="http://www.acm.org/about-acm/get-involved">Volunteer</a></li> <li><a href="/">Home</a></li> <li class="hide-for-small"> <form class="acm-search-form" id="form_1"> <label for="input_1"> <span class="visually-hidden">Search Input</span> </label> <input type="text" name="q" id="input_1" class="acm-searchbox-input st-default-search-input"/> <label for="search-site_1" class="toggle"> <span class="visually-hidden">Search Submit</span> <i class="fa fa-search left"></i> <input type="button" class="acm-searchbox-submit left" value="Search" name="search-site_1" id="search-site_1" /> </label> </form> </li> </ul> </div> </div> <script type="text/javascript"> (function(w,d,t,u,n,s,e){w['SwiftypeObject']=n;w[n]=w[n]||function(){ (w[n].q=w[n].q||[]).push(arguments);};s=d.createElement(t); e=d.getElementsByTagName(t)[0];s.async=1;s.src=u;e.parentNode.insertBefore(s,e); })(window,document,'script','//s.swiftypecdn.com/install/v2/st.js','_st'); _st('install','CQP6y65EjuZ71VuVBwbZ','2.0.0'); </script> <nav class="top-bar main-nav" data-topbar data-options="is_hover: false"> <ul class="title-area"> <li class="toggle-topbar menu-icon"><a href="/#"><span></span> </a></li> </ul> <section id="mobile-nav-topbar" class="top-bar-section"> <div class="mobile-links"> <div class="btn-group"> <a class="btn btn-primary" role="button" href="http://www.acm.org/membership/join">Join</a> <a class="btn btn-primary" role="button" href="http://www.acm.org/about-acm/get-involved">Volunteer</a> <a class="btn btn-primary" role="button" href="/">Home</a> </div> <div class="mobile-search"> <form class="acm-search-form" id="mobile_form_1"> <i class="fa fa-search left"></i> <label class="" for="search_mobile_1">Search</label> <input type="text" id="search_mobile_1" class="acm-searchbox-input st-default-search-input" name="q"/> </form> </div> </div> <ul> <li class="has-dropdown not-click"><a href="#">About ACM Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about" class="first">About ACM Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/about/purpose" title="Purpose" >Purpose</a></li> <li><a href="/about/how-to" title="How To" >How To</a></li> <li><a href="/about/policies" title="Policies" >Policies</a></li> <li><a href="/about/nominate" title="Become or Nominate a Speaker" >Become or Nominate a Speaker</a></li> <li><a href="/about/request" title="Request a Speaker" >Request a Speaker</a></li> <li><a href="/calendar" title="Lectures Calendar" >Lectures Calendar</a></li> <li><a href="/about/committee" title="ACM Speakers Committee" >ACM Speakers Committee</a></li> <li><a href="https://campus2.acm.org/public/speakers/feedback.cfm" title="Feedback" >Feedback</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Speakers</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/speakers" class="first">Browse Our Speakers</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar" >Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Topics</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/topics" class="first">Browse Our Topics</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar" >Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Countries</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/countries" class="first">Browse Countries in which Our Speakers Reside</a> <ul class="infonav__linkList-list clearfix"> <li><a href="/calendar" title="Lectures Calendar" >Lectures Calendar</a></li> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Request a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/request" class="first">Request a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Nominate a Speaker</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/nominate" class="first">Become or Nominate a Speaker</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Purpose</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-mission-and-history" class="first">Mission and History</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> <li class="has-dropdown not-click"><a href="#">Governance</a> <div class="dropdown clearfix"> <ul class="infonav clearfix"> <li class="infonav__linkList clearfix"> <a href="/about/speakers-committee" class="first">Speakers Committee</a> <ul class="infonav__linkList-list clearfix"> </ul> </li> <li class="infonav__landingPage"> <div> <p class="first">About the ACM Distinguished Speakers</p> <p>Book an ACM Distinguished Speaker for your next event and deliver compelling and insightful content to your audience. ACM Distinguished Speakers are renowned thought leaders in computing speaking about the most important topics in the field today.</p></div> </li> <li class="infonav__ctaList"> <div class="infonav__ctaList-cta"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/membership/dsp/doris-lee-dsp.jpg" alt="Doris Lee"></a><div class="cta-text"> <a href='https://speakers.acm.org/speakers/lee_18369' target='_blank'>Meet Featured ACM Distinguished Speaker Doris Lee</a></div> </div> <div class="infonav__ctaList-cta"> <a href='/nominate' ><img src="/binaries/ctaimagelarge/content/gallery/acm/ctas/dsp_logo.jpg" alt="dsp_logo.jpg"></a><div class="cta-text"> <a href='/nominate' >Become an ACM Distinguished Speaker!</a></div> </div> </li> </ul> </div> </li> </ul> </section> </nav> </div> <div id="main" > <div class="article" id="maincontent" tabindex="-1"> <div class="row"> <div class="columns small-12"> <ul class="breadcrumbs"> <li><a href="/">Home</a></li> <li><a href="/lectures">Lectures</a></li> <li class="current">Compact Data Structures meet Databases</li> </ul> </div> </div> <div class="speakers"> <div class="row lecture__section"> <h1>Compact Data Structures meet Databases</h1> <span> <strong>Speaker: </strong> <a href="../speakers/navarro_18834">Gonzalo Navarro</a> <span> – Santiago, Chile</span> </span><br/> <span> <strong>Topic(s): </strong> <a href="../topics/computational-theory-algorithms-and-mathematics">Computational Theory, Algorithms and Mathematics</a> , <a href="../topics/information-systems-search-information-retrieval-database-systems-data-mining-data-science">Information Systems, Search, Information Retrieval, Database Systems, Data Mining, Data Science</a> </span> </div> <div class="row lecture__section"> <h2>Abstract</h2> <p class="MsoNormal"> We describe two success stories on the application of compact data structures (cds) to solve the problem of the excessively redundant space requirements posed by worst-case-optimal (wco) algorithms for multijoins in databases, and particularly basic graph patterns on graph databases.<span> </span>The aim of cds is to represent the data and additional data structures on it, using total space close to that of the plain (and, sometimes, compressed) data, while efficiently simulating the data structure operations. Cds turn out to be a perfect approach for the described problem: We designed and implemented cds that effectively use space close to that of the plain or compressed data, which is orders of magnitude less than existing systems, while retaining worst-case optimality and performing competitively with those systems in querytime, sometimes being even considerably faster. </p> </div> <div class="row lecture__section"> <h2>About this Lecture</h2> <span> <strong>Number of Slides: </strong> 60</span><br/> <span> <strong>Duration: </strong> 60 minutes </span><br/> <span> <strong>Languages Available: </strong> English</span><br/> <span> <strong>Last Updated: </strong> <span id="lecDate"></span> </span> </div> <div class="row lecture__section"> <h2>Request this Lecture</h2> <p>To request this particular lecture, please complete this <a href="https://services.acm.org/public/speakers/request_lecture.cfm?lecture_id=15645" target="_blank">online form.</a> </p> </div> <div class="row lecture__section"> <h2>Request a Tour</h2> <p>To request a tour with this speaker, please complete this <a href="https://services.acm.org/public/speakers/request_tour.cfm?lecturer_id=18834" target="_blank">online form.</a> </p> <p>All requests will be sent to ACM headquarters for review.</p> </div> </div> </div> <script> var updated = document.getElementById('lecDate'); var d = new Date(parseInt('1695340800000')); updated.innerHTML = d.getDate() + '/' + (d.getMonth() + 1) + '/' + d.getFullYear(); </script> </div> <div class="row"> <footer> <nav> <div class="footer-nav"> <ul class="footer-nav-lists"> <li> About ACM</li> <li><a href="https://www.acm.org/about-acm" title="About ACM">About ACM</a></li> <li><a href="https://www.acm.org/about-acm/get-involved" title="About ACM">Volunteer</a></li> </ul> <ul class="footer-nav-lists"> <li> Membership</li> <li><a href="https://www.acm.org/membership/join-acm" title="Membership">Join ACM</a></li> <li><a href="https://www.acm.org/membership/acm-membership-renewal" title="Membership">Renew My Membership</a></li> <li><a href="https://www.acm.org/membership/membership-options" title="Membership">Membership Options</a></li> <li><a href="https://www.acm.org/membership/membership-benefits" title="Membership">Membership Benefits</a></li> <li><a href="https://www.acm.org/membership/myacm-at-a-glance" title="Membership">myACM Sign-In</a></li> </ul> <ul class="footer-nav-lists"> <li> Publications</li> <li><a href="https://www.acm.org/publications" title="Publications">About Publications</a></li> <li><a href="https://www.acm.org/publications/digital-library" title="Publications">Digital Library</a></li> <li><a href="https://authors.acm.org/" title="Publications">Submit A Paper</a></li> </ul> <ul class="footer-nav-lists"> <li> Chapters</li> <li><a href="https://www.acm.org/chapters/chapter-administrative-interface" title="Chapters">Chapter Administrative Interface</a></li> <li><a href="https://www.acm.org/chapters/local-activities" title="Chapters">Chapter Activities Calendar</a></li> <li><a href="https://www.acm.org/chapters/start-chapter" title="Chapters">Start A Chapter</a></li> </ul> <ul class="footer-nav-lists"> <li> Awards</li> <li><a href="https://awards.acm.org" title="Awards">About ACM's Awards</a></li> </ul> <ul class="footer-nav-lists"> <li> Conferences</li> <li><a href="https://www.acm.org/conferences" title="Conferences">ACM's Conferences</a></li> </ul> <ul class="footer-nav-lists"> <li> Code of Ethics</li> <li><a href="https://www.acm.org/code-of-ethics" title="Code of Ethics">ACM's Code of Ethics</a></li> <li><a href="https://www.acm.org/code-of-ethics/enforcement-procedures" title="Code of Ethics">Enforcement Procedures</a></li> </ul> <ul class="footer-nav-lists"> <li> Media Center</li> <li><a href="https://www.acm.org/media-center" title="Media Center">ACM Media Center</a></li> </ul> </div> </nav> <div> <div> <div class="logo_social_group"> <hr /> <img src='/binaries/content/gallery/acm/logos/logo_footer_acm.png' alt='ACM Logo' /> <ul class="footer__social"> <li> <a href="https://www.facebook.com/AssociationForComputingMachinery/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_facebook.png" alt="Facebook logo" /> </a> </li> <li> <a href="https://twitter.com/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_x_twitter.png" alt="Twitter logo" /> </a> </li> <li> <a href="https://www.linkedin.com/company/association-for-computing-machinery" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_linkedin.png" alt="LinkedIn logo" /> </a> </li> <li> <a href="https://www.reddit.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_reddit.png" alt="Reddit logo" /> </a> </li> <li> <a href="https://www.youtube.com/user/TheOfficialACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_youtube.png" alt="YouTube logo" /> </a> </li> <li> <a href="https://www.instagram.com/theofficialacm/" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_instagram.png" alt="Instagram" /> </a> </li> <li> <a href="https://www.flickr.com/photos/theofficialacm" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_flickr.png" alt="Flickr" /> </a> </li> <li> <a href="https://mastodon.acm.org/@ACM" target="_blank"> <img src="/binaries/content/gallery/acm/social-media/icon_mastodon.png" alt="Mastodon" /> </a> </li> </ul> </div> </div> </div> <div> <div> <ul class="footer__legal clearfix"> <li><a href="/">Home</a></li> <li><a href="/">SRC Home</a></li> <li><a href="https://www.acm.org">ACM Home</a></li> <li><a href="/sitemap">Sitemap</a></li> <li><a href="https://www.acm.org/about-acm/contact-us">Contact Us</a></li> <li><a href="https://www.acm.org/membership/acm-hq-contact">Member Services</a></li> <li><a href="https://www.acm.org/about-acm/privacy-policy">Privacy Policy</a></li> <li><a href="https://www.acm.org/accessibility">Accessibility</a></li> <li class="footer__copyright">Copyright © 2024, ACM, Inc</li> </ul> </div> </div> </footer> </div> <script data-cookieconsent="ignore" type="text/javascript" src="/js/acm.js?antiCache=1716999351349"></script> <script>$(document).foundation();</script> <script type="text/javascript" src="//s7.addthis.com/js/300/addthis_widget.js#pubid=ra-5654b74db1437702" async="async"></script> <script async src="https://www.googletagmanager.com/gtag/js?id=UA-115744816-1"></script> <script> window.dataLayer = window.dataLayer || []; function gtag(){ dataLayer.push(arguments); } gtag('js', new Date()); gtag('config', 'UA-115744816-1'); </script> </body> </html>