1<!DOCTYPE html> 2<html lang="en"> 3<!-- Beautiful Jekyll 6.0.1 | Copyright Dean Attali 2023 --> 4<head> 5 <meta charset="utf-8"> 6 <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> 7 8 9 10 11 12 <title>Research Projects</title> 13 14 15 16 <meta name="author" content="Seokki Lee"> 17 18 19 <meta name="description" content="## Database and Data Provenance ### Why and Why-not Provenace Summaries for Queries with Negation Provenance explains produced data over database operations such that which tuple (row) in the data generated by a query is derived from which tuple in the input data through which operation(s). Similarly, why-not provenance informs..."> 20 21 22 23 24 25 26 <link rel="alternate" type="application/rss+xml" title="UC Database Group" href="https://shek21.github.io/feed.xml"> 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 <link href="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/css/bootstrap.min.css" rel="stylesheet" integrity="sha384-Vkoo8x4CGsO3+Hhxv8T/Q5PaXtkKtu6ug5TOeNV6gBiFeWPGFN9MuhOf23Q9Ifjh" crossorigin="anonymous"> 42 43 44 45 46 <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.12.1/css/all.min.css"> 47 48 49 50 51 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Lora:400,700,400italic,700italic"> 52 53 54 55 56 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300italic,400italic,600italic,700italic,800italic,400,300,600,700,800"> 57 58 59 60 61 62 63 64 <link rel="stylesheet" href="/assets/css/bootstrap-social.css"> 65 66 <link rel="stylesheet" href="/assets/css/beautifuljekyll.css"> 67 68 69 70 71 72 73 74 75 76 77 78 79 <meta property="og:site_name" content="UC Database Group"> 80 <meta property="og:title" content="Research Projects"> 81 <meta property="og:description" content="## Database and Data Provenance ### Why and Why-not Provenace Summaries for Queries with Negation Provenance explains produced data over database operations such that which tuple (row) in the data generated by a query is derived from which tuple in the input data through which operation(s). Similarly, why-not provenance informs..."> 82 83 84 <meta property="og:image" content="https://shek21.github.io/assets/img/seokki.png"> 85 86 87 88 <meta property="og:type" content="website"> 89 <meta property="og:url" content="https://shek21.github.io/research/"> 90 <link rel="canonical" href="https://shek21.github.io/research/"> 91 92 93 94 <meta name="twitter:card" content="summary"> 95 96 <meta name="twitter:site" content="@"> 97 <meta name="twitter:creator" content="@"> 98 99 <meta property="twitter:title" content="Research Projects"> 100 <meta property="twitter:description" content="## Database and Data Provenance ### Why and Why-not Provenace Summaries for Queries with Negation Provenance explains produced data over database operations such that which tuple (row) in the data generated by a query is derived from which tuple in the input data through which operation(s). Similarly, why-not provenance informs..."> 101 102 103 <meta name="twitter:image" content="https://shek21.github.io/assets/img/seokki.png"> 104 105 106 107 108 109 110 111 112 113 114 115 116</head> 117 118 119<body> 120 121 122 123 <nav class="navbar navbar-expand-xl navbar-light fixed-top navbar-custom top-nav-regular"><a class="navbar-brand" href="https://shek21.github.io/">UC Database Group</a><button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#main-navbar" aria-controls="main-navbar" aria-expanded="false" aria-label="Toggle navigation"> 124 <span class="navbar-toggler-icon"></span> 125 </button> 126 127 <div class="collapse navbar-collapse" id="main-navbar"> 128 <ul class="navbar-nav ml-auto"> 129 <li class="nav-item"> 130 <a class="nav-link" href="/research">Research</a> 131 </li> 132 <li class="nav-item"> 133 <a class="nav-link" href="/publications">Publications</a> 134 </li> 135 <li class="nav-item"> 136 <a class="nav-link" href="/teaching">Teaching</a> 137 </li> 138 <li class="nav-item"> 139 <a class="nav-link" href="/people">People</a> 140 </li> 141 <li class="nav-item"> 142 <a class="nav-link" href="/cv">CV</a> 143 </li> 144 <li class="nav-item"> 145 <a class="nav-link" id="nav-search-link" href="#" title="Search">
146 <span id="nav-search-icon" class="fa fa-search"></span> 147 <span id="nav-search-text">Search</span> 148 </a> 149 </li></ul> 150 </div> 151 152 153 154 155 <div class="avatar-container"> 156 <div class="avatar-img-border"> 157 <a href="https://shek21.github.io/"> 158 <img alt="Navigation bar avatar" class="avatar-img" src="/assets/img/seokki.png" /> 159 </a> 160 </div> 161 </div> 162 163 164</nav> 165 166 167 168<div id="beautifuljekyll-search-overlay"> 169 170 <div id="nav-search-exit" title="Exit search">â</div> 171 <input type="text" id="nav-search-input" placeholder="Search"> 172 <ul id="search-results-container"></ul> 173 174
174<script src="https://unpkg.com/simple-jekyll-search@latest/dest/simple-jekyll-search.min.js"></script>
174 175
175<script> 176 var searchjson = '[ \ 177 \ 178 { \ 179 "title" : "A paper is accepted by ACM TaPP (W3C)", \ 180 "desc" : "A paper is accepted by ACM TaPP (W3C)", \ 181 "category" : "big provenancesampling", \ 182 "url" : "/2023-01-31-tapp-sampling/", \ 183 "date" : "January 31, 2023" \ 184 }, \ 185 \ 186 { \ 187 "title" : "A paper is accepted by IEEE ICDEW", \ 188 "desc" : "A paper is accepted by IEEE ICDEW", \ 189 "category" : "mlprovenanceexplanations", \ 190 "url" : "/2023-01-31-icdew-mlprov/", \ 191 "date" : "January 31, 2023" \ 192 }, \ 193 \ 194 { \ 195 "title" : "A paper is accepted by ACM TaPP (SIGMOD)", \ 196 "desc" : "A paper is accepted by ACM TaPP (SIGMOD)", \ 197 "category" : "provenanceinformation gaindata sharing", \ 198 "url" : "/2022-06-22-tapp-ig/", \ 199 "date" : "June 22, 2022" \ 200 }, \ 201 \ 202 \ 203 { \ 204 "title" : "About me", \ 205 "desc" : "About me", \ 206 "category" : "page", \ 207 "url" : "/aboutme/", \ 208 "date" : "January 1, 1970" \ 209 }, \ 210 \ 211 { \ 212 "title" : "Curriculum Vitae", \ 213 "desc" : "Curriculum Vitae", \ 214 "category" : "page", \ 215 "url" : "/cv/", \ 216 "date" : "January 1, 1970" \ 217 }, \ 218 \ 219 { \ 220 "title" : "UC Database Group (UCDBG)", \ 221 "desc" : "UC Database Group (UCDBG)", \ 222 "category" : "page", \ 223 "url" : "/", \ 224 "date" : "January 1, 1970" \ 225 }, \ 226 \ 227 { \ 228 "title" : "Team Members", \ 229 "desc" : "Team Members", \ 230 "category" : "page", \ 231 "url" : "/people/", \ 232 "date" : "January 1, 1970" \ 233 }, \ 234 \ 235 { \ 236 "title" : "Publications", \ 237 "desc" : "Publications", \ 238 "category" : "page", \ 239 "url" : "/publications/", \ 240 "date" : "January 1, 1970" \ 241 }, \ 242 \ 243 { \ 244 "title" : "Research Projects", \ 245 "desc" : "Research Projects", \ 246 "category" : "page", \ 247 "url" : "/research/", \ 248 "date" : "January 1, 1970" \ 249 }, \ 250 \ 251 { \ 252 "title" : "Tag Index", \ 253 "desc" : "Tag Index", \ 254 "category" : "page", \ 255 "url" : "/tags/", \ 256 "date" : "January 1, 1970" \ 257 }, \ 258 \ 259 { \ 260 "title" : "Teaching", \ 261 "desc" : "Teaching", \ 262 "category" : "page", \ 263 "url" : "/teaching/", \ 264 "date" : "January 1, 1970" \ 265 } \ 266 \ 267 ]'; 268 searchjson = JSON.parse(searchjson); 269 270 var sjs = SimpleJekyllSearch({ 271 searchInput: document.getElementById('nav-search-input'), 272 resultsContainer: document.getElementById('search-results-container'), 273 json: searchjson 274 }); 275 </script>
275 276</div> 277 278 279 280 281 282 283 284 285 286<header class="header-section "> 287<div class="intro-header "> 288 289 <div class="container-md"> 290 <div class="row"> 291 <div class="col-xl-8 offset-xl-2 col-lg-10 offset-lg-1"> 292 <div class="page-heading"> 293 <h1>Research Projects</h1> 294 295 296 297 </div> 298 </div> 299 </div> 300 </div> 301 302 303</div> 304 305 306 307</header> 308 309 310<main class=" container-md "> 311 <div class="row"> 312 <div class=" col-xl-8 offset-xl-2 col-lg-10 offset-lg-1 "> 313 314 315 <h2 id="database-and-data-provenance">Database and Data Provenance</h2> 316 317<h3 id="why-and-why-not-provenace-summaries-for-queries-with-negation">Why and Why-not Provenace Summaries for Queries with Negation</h3> 318<p>Provenance explains produced data over database operations such that which tuple (row) in the data generated by a query is derived from which tuple in the input data through which operation(s). Similarly, why-not provenance informs why and how tuples are missing in the produced data. <a href="https://github.com/UCDBG/PUG">PUG (Provenance Unification through Graphs)</a> is a middleware system that efficiently captures provenance for a given data and query. PUG introduces a novel approach for computing unified why and why-not provenance. The technique used in PUG is the first practical method that computes explanations using samples of why-not provenance over real-world datasets and queries with negation. The system is (particularly) useful for understanding processed data, debugging data processing pipelines, and so on. In the following, research (including development) opportunities which add more power to PUG are listed.</p> 319 320<p><img src="/assets/img/pug_arch.png" alt="PUG" /></p> 321 322<h3 id="efficient-sampling-for-big-provenance">Efficient Sampling for Big Provenance</h3> 323<p>Provenance has been studied extensively to explain existing and missing results for many applications while focusing on scalability and usability challenges. Recently, techniques that efficiently compute a compact representation of provenance have been introduced. In this work, we introduce a practical solution that computes a sample of provenance for existing results without computing full provenance. Our technique computes a sample of provenance based on the distribution of provenance wrt the query result that is estimated from the distribution of input data while considering the correlation among the data. The preliminary evaluation demonstrates that comparing to the naive approach our method efficiently computes a sample of (large size of) provenance with low errors. The initial paper is available <a href="https://dl.acm.org/doi/pdf/10.1145/3543873.3587556">here</a>.</p> 324 325<h3 id="hybrid-explanations-and-repairs">Hybrid Explanations and Repairs</h3> 326<p>Prior work on explaining missing (unexpected) query results identifes which parts of the query or data are responsible for the erroneous result or repairs the query or data to fx such errors. The problem of generating repairs is typically expressed as an optimization problem, i.e., a single repair is returned that is optimal wrt. to some criterion such as minimizing the repairâs side efects. However, such an optimization objective may not concretely model a userâs (often hard to formalize) notion of which repair is âcorrectâ. In this paper, we motivate hybrid explanations and repairs, i.e., that fix both the query and the data. Instead of returning one âoptimalâ repair, we argue for an approach that empowers the user to explore the space of possible repairs efectively. We also present a proof-of-concept implementation and outline open research problems. The initial paper is available <a href="https://dl.acm.org/doi/pdf/10.1145/3543873.3587565">here</a></p> 327 328<h2 id="applications-of-data-management-and-data-provenance">Applications of Data Management and Data Provenance</h2> 329 330<h3 id="provenance-based-ml-explanations">Provenance-based ML Explanations</h3> 331<!-- The explainability of machine learning (ML) has emerged as a crucial subfield, yet the computational cost of generating explanations remains high [29]. For instance, computing feature impact and data instance contribution involves dealing with an exponential number of coalitions of feature values and permutations of input data. Furthermore, existing explanations lack granularity and generality, failing to properly explain the effects of subsets of data instances and features that significantly impact the model. While methods have been proposed for approximating explanations and determining the influence of individual instances using influence functions, these may not precisely capture the modelâs actual operational status, and axiomatic properties might not hold under approximations. The widely used explanations, namely global and local explanations, fall short in providing insights into the effects of subsets of data instances and features. --> 332<p>This project develops a generic tool, which we call Generic Provenance-based System for Machine Learning (GPML), designed to facilitate explainable ML through provenance. In the context of an ML task, GPML efficie
332ntly captures provenance and generates explanations during the model training process. Our framework achieves this by transforming the given ML model into a Datalog program, a logic-based declarative database query language, utilizing and expanding formal semantics to accommodate a broad range of ML models, including neural networks. The provenance component within GPML efficiently captures provenance by enhancing previous techniques through the rewriting of the Datalog program. The resulting provenance is comprehensive enough to compute more detailed (explaining the impact of subsets of features and data instances) and unified (providing both global and local) explanations. The explanation generation component of GPML will then produce these explanations based on the captured provenance, eliminating the need for model retraining. GPMLâs output comprises a set of explanations detailing the contributions of (sub- populations of) features and data instances, in addition to the modelâs prediction. The initial work of this research project is outlined <a href="https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10148106">here</a>.</p> 333 334<h3 id="exploring-provenance-for-explainable-information-gain">Exploring Provenance for Explainable Information Gain</h3> 335<p>In recent years, a large amount of data is collected from multiple sources and the demands for analyzing these data have increased enormously. Data sharing is a valuable part of this data-intensive and collaborative environment due to the synergies and added values created by multi-modal datasets generated from different sources. In this work, we introduce a technique that quantifies the degree of information gain (IG) that is obtained over data sharing. The IG is computed based on the distance between data that are integrated after the sharing. Our method captures both where (to compute the IG over values) and how provenance (to find matching records) and accurately computes the IG based on them. To provide better understanding on the data sharing, we develop a technique that computes meaningful summaries of data that highly contribute to IG. For that, we define four metrics that allow to provide such meaningful explanations. We conduct a set of experiments to demonstrate the performance and accuracy of our approach comparing to naive method using real-world datasets. The initial version of the paper is available <a href="https://dl.acm.org/doi/pdf/10.1145/3530800.3534534">here</a>.</p> 336 337 338 339 340 341 342 </div> 343 </div> 344</main> 345 346 347 <footer> 348 <div class="container-md beautiful-jekyll-footer"> 349 <div class="row"> 350 <div class="col-xl-8 offset-xl-2 col-lg-10 offset-lg-1"> 351 352<ul class="list-inline text-center footer-links"><li class="list-inline-item"> 353 <a href="mailto:[email protected]" title="Email me"> 354 <span class="fa-stack fa-lg" aria-hidden="true"> 355 <i class="fas fa-circle fa-stack-2x"></i> 356 <i class="fas fa-envelope fa-stack-1x fa-inverse"></i> 357 </span> 358 <span class="sr-only">Email me</span> 359 </a> 360 </li><li class="list-inline-item"> 361 <a href="/feed.xml" title="RSS"> 362 <span class="fa-stack fa-lg" aria-hidden="true"> 363 <i class="fas fa-circle fa-stack-2x"></i> 364 <i class="fas fa-rss fa-stack-1x fa-inverse"></i> 365 </span> 366 <span class="sr-only">RSS</span> 367 </a> 368 </li><li class="list-inline-item"> 369 <a href="https://github.com/UCDBG" title="GitHub"> 370 <span class="fa-stack fa-lg" aria-hidden="true"> 371 <i class="fas fa-circle fa-stack-2x"></i> 372 <i class="fab fa-github fa-stack-1x fa-inverse"></i> 373 </span> 374 <span class="sr-only">GitHub</span> 375 </a> 376 </li></ul> 377 378 379 <p class="copyright text-muted"> 380 381 Seokki Lee 382 • 383 384 2024 385 386 387 • 388 <span class="author-site"> 389 <a href="https://shek21.github.io/">UCDBG Website</a> 390 </span> 391 392 393 394 395 396 397 </p> 398 <p class="theme-by text-muted"> 399 Powered by 400 <a href="https://beautifuljekyll.com">Beautiful Jekyll</a> 401 </p> 402 </div> 403 </div> 404 </div> 405</footer> 406 407 408 409 410 411
411<script src="https://code.jquery.com/jquery-3.5.1.slim.min.js" integrity="sha256-4+XzXVhsDmqanXGHaHvgh1gMQKX40OUvDEBTu8JcmNs=" crossorigin="anonymous"></script>
411 412 413 414 415 416
416<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/umd/popper.min.js" integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
416 417 418 419 420 421
421<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.4.1/js/bootstrap.min.js" integrity="sha384-wfSDF2E50Y2D1uUdj0O3uMBJnjuUD4Ih7YwaYd1iqfktj0Uod8GCExl3Og8ifwB6" crossorigin="anonymous"></script>
421 422 423 424 425 426 427 428 429 <!-- doing something a bit funky here because I want to be careful not to include JQuery twice! --> 430 431
431<script src="/assets/js/beautifuljekyll.js"></script>
431 432 433 434 435 436 437 438 439 440 441 442 443</body> 444</html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.