Master’s Thesis Presentation • Data Systems — Domain Ordering and Box Cover Problems for Beyond Worst-Case Join ProcessingExport this event to calendar

Tuesday, September 3, 2019 — 10:00 AM EDT

Kaleb Alway, Master’s candidate
David R. Cheriton School of Computer Science

Recent developments in join query processing have lead to join algorithms with runtime proportional to the minimum size of a geometric box certificate for the query instance. Many query instances admit a smaller box certificate when the elements of the attributes' domains are ordered differently. Finding the domain ordering which minimizes the box certificate size improves the runtime of join queries. We present hardness results for this and related box cover problems, as well as algorithms which approximate special cases of the problem.

Location 
DC - William G. Davis Computer Research Centre
2310
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2020 (1)
    1. January (1)
  2. 2019 (251)
    1. December (17)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (22)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)