@book{gondran08dioids,
author = {Gondran, Michel and Minoux, Michel},
doi = {10.1007/978-0-387-75450-5},
publisher = {Springer},
title = {Graphs, Dioids and Semirings: New Models and Algorithms (Operations Research/Computer Science Interfaces Series)},
year = {2008}
}
@article{mohri02semirings,
author = {Mohri, Mehryar},
title = {Semiring Frameworks and Algorithms for Shortest-Distance Problems},
year = {2002},
volume = {7},
number = {3},
journal = {J. Autom. Lang. Comb.},
month = {Jan},
pages = {321–350},
url = {http://www.jalc.de/issues/2002/issue_7_3/abs-321.pdf }
}
@article{aji00distrib,
author = {S. M. {Aji} and R. J. {McEliece}},
journal = {IEEE Transactions on Information Theory},
title = {The generalized distributive law},
year = {2000},
volume = {46},
number = {2},
pages = {325-343},
doi = {10.1109/18.825794}
}
@article{alon97cycles,
author = {Alon, N. and Yuster, R. and Zwick, U.},
doi = {10.1007/BF02523189},
journal = {Algorithmica},
month = {Mar},
number = {3},
pages = {209--223},
title = {Finding and counting given length cycles},
volume = {17},
year = {1997}
}
@inproceedings{zhang06opt,
author = {Zhang, Zhen and Hwang, Seung-won and Chang, Kevin Chen-Chuan and Wang, Min and Lang, Christian A. and Chang, Yuan-chi},
title = {Boolean + Ranking: Querying a Database by k-Constrained Optimization},
year = {2006},
doi = {10.1145/1142473.1142515},
booktitle = {SIGMOD},
pages = {359–370}
}
@inproceedings{das06views,
author = {Das, Gautam and Gunopulos, Dimitrios and Koudas, Nick and Tsirogiannis, Dimitris},
title = {Answering Top-k Queries Using Views},
year = {2006},
booktitle = {VLDB},
pages = {451–462},
url = {http://www.vldb.org/conf/2006/p451-das.pdf}
}
@inproceedings{hristidis01prefer,
author = {Hristidis, Vagelis and Koudas, Nick and Papakonstantinou, Yannis},
title = {PREFER: A System for the Efficient Execution of Multi-Parametric Ranked Queries},
year = {2001},
doi = {10.1145/375663.375690},
booktitle = {SIGMOD},
pages = {259–270}
}
@inproceedings{chang00onion,
author = {Chang, Yuan-Chi and Bergman, Lawrence and Castelli, Vittorio and Li, Chung-Sheng and Lo, Ming-Ling and Smith, John R.},
title = {The Onion Technique: Indexing for Linear Optimization Queries},
year = {2000},
doi = {10.1145/342009.335433},
booktitle = {SIGMOD},
pages = {391–402}
}
@inproceedings{tsaparas03topk,
author = {Tsaparas, Panayiotis and Palpanas, Themistoklis and Kotidis, Yannis and Koudas, Nick and Srivastava, Divesh},
booktitle = {ICDE},
doi = {10.1109/ICDE.2003.1260799},
pages = {277--288},
title = {Ranked join indices},
year = {2003}
}
@inproceedings{bruno02topk,
author = {Bruno, Nicolas and Gravano, Luis and Marian, Amelie},
booktitle = {ICDE},
doi = {10.1109/ICDE.2002.994751},
pages = {369--380},
title = {Evaluating top-k queries over web-accessible databases},
year = {2002}
}
@inproceedings{DBLP:conf/vldb/BastMSTW06,
author = {H. Bast and Debapriyo Majumdar and Ralf Schenkel and Martin Theobald and Gerhard Weikum},
booktitle = {VLDB},
pages = {475--486},
title = {{IO}-Top-$k$: Index-access Optimized Top-$k$ Query Processing},
url = {https://dl.acm.org/doi/10.5555/1182635.1164169},
year = {2006}
}
@article{TziavelisAGRY:2020,
author = {Nikolaos Tziavelis and Deepak Ajwani and Wolfgang Gatterbauer and Mirek Riedewald and Xiaofeng Yang},
title = {Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries},
journal = {PVLDB},
volume = {13},
number = {9},
pages = {1582--1597},
year = {2020},
doi = {10.14778/3397230.3397250}
}
@article{fagin99fa,
author = {Fagin, Ronald},
title = {Combining fuzzy information from multiple systems},
doi = {10.1006/jcss.1998.1600},
number = {1},
pages = {83--99},
volume = {58},
journal = {Journal of Computer and System Sciences},
publisher = {Elsevier},
year = {1999}
}
@article{chang15enumeration,
author = {Chang, Lijun and Lin, Xuemin and Zhang, Wenjie and Yu, Jeffrey Xu and Zhang, Ying and Qin, Lu},
title = {Optimal enumeration: Efficient top-k tree matching},
doi = {10.14778/2735479.2735486},
number = {5},
pages = {533--544},
volume = {8},
journal = {PVLDB},
year = {2015}
}
@inproceedings{navarro19wco,
author = {Navarro, Gonzalo and Reutter, Juan L and Rojas-Ledesma, Javiel},
booktitle = {ICDT},
title = {Optimal Joins using Compact Data Structures},
url = {https://arxiv.org/abs/1908.01812},
year = {2020}
}
@article{ngo2018worst,
author = {Ngo, Hung Q and Porat, Ely and R{\'e}, Christopher and Rudra, Atri},
title = {Worst-case optimal join algorithms},
doi = {https://doi.org/10.1145/3180143},
number = {3},
pages = {16},
volume = {65},
journal = {J. ACM},
publisher = {ACM},
year = {2018}
}
@inproceedings{abo16faq,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q and Rudra, Atri},
booktitle = {PODS},
title = {FAQ: questions asked frequently},
doi = {10.1145/2902251.2902280},
pages = {13--28},
year = {2016}
}
@inproceedings{Berkholz:2017:ACQ:3034786.3034789,
author = {Berkholz, Christoph and Keppeler, Jens and Schweikardt, Nicole},
booktitle = {PODS},
title = {Answering Conjunctive Queries Under Updates},
doi = {10.1145/3034786.3034789},
isbn = {978-1-4503-4198-1},
pages = {303--318},
acmid = {3034789},
date-added = {2018-11-16 17:16:31 -0500},
date-modified = {2019-10-31 21:50:05 -0400},
keywords = {constant delay enumeration, counting complexity, dichotomy, dynamic algorithms, online matrix-vector multiplication, query evaluation},
numpages = {16},
year = {2017}
}
@article{ROBERTSON1986309,
author = {Neil Robertson and P.D Seymour},
title = {Graph minors. II. Algorithmic aspects of tree-width},
doi = {https://doi.org/10.1016/0196-6774(86)90023-4},
issn = {0196-6774},
number = {3},
pages = {309 - 322},
volume = {7},
journal = {Journal of Algorithms},
year = {1986}
}
@inproceedings{hogan19sparql,
author = {Hogan, Aidan and Riveros, Cristian and Rojas, Carlos and Soto, Adri{\'a}n},
booktitle = {ISWC},
title = {A Worst-Case Optimal Join Algorithm for SPARQL},
doi = {10.1007/978-3-030-30793-6\_15},
pages = {258--275},
year = {2019}
}
@inproceedings{AboKhamis:2019:FAQ:3294052.3319694,
author = {Abo Khamis, Mahmoud and Curtin, Ryan R. and Moseley, Benjamin and Ngo, Hung Q. and Nguyen, XuanLong and Olteanu, Dan and Schleich, Maximilian},
booktitle = {PODS},
title = {On Functional Aggregate Queries with Additive Inequalities},
doi = {10.1145/3294052.3319694},
isbn = {978-1-4503-6227-6},
pages = {414--431},
acmid = {3319694},
numpages = {18},
year = {2019}
}
@inproceedings{natsev01,
author = {Natsev, Apostol and Chang, Yuan-Chi and Smith, John R and Li, Chung-Sheng and Vitter, Jeffrey Scott},
booktitle = {VLDB},
title = {Supporting incremental join queries on ranked inputs},
pages = {281--290},
url = {http://www.vldb.org/conf/2001/P281.pdf},
year = {2001}
}
@article{greco17consistency,
author = {Greco, Gianluigi and Scarcello, Francesco},
title = {The power of local consistency in conjunctive queries and constraint satisfaction problems},
doi = {10.1137/16M1090272},
number = {3},
pages = {1111--1145},
volume = {46},
journal = {SIAM Journal on Computing},
publisher = {SIAM},
year = {2017}
}
@article{hoffman59shortest,
author = {Hoffman, Walter and Pavley, Richard},
title = {A Method for the Solution of the $N$th Best Path Problem},
doi = {10.1145/320998.321004},
number = {4},
pages = {506--514},
volume = {6},
journal = {J. ACM},
publisher = {ACM},
year = {1959}
}
@article{DBLP:journals/ai/Dechter92,
author = {Rina Dechter},
title = {From Local to Global Consistency},
doi = {10.1016/0004-3702(92)90043-W},
number = {1},
pages = {87--108},
volume = {55},
journal = {Artif. Intell.},
year = {1992}
}
@article{joglekar18degree,
author = {Joglekar, Manas and R{\'e}, Christopher},
title = {It's All a Matter of Degree},
doi = {10.1007/s00224-017-9811-8},
number = {4},
pages = {810--853},
volume = {62},
journal = {Theory of Computing Systems},
publisher = {Springer},
year = {2018}
}
@article{DBLP:journals/vldb/FinkHO13,
author = {Robert Fink and Jiewen Huang and Dan Olteanu},
title = {Anytime approximation in probabilistic databases},
doi = {10.1007/s00778-013-0310-5},
number = {6},
pages = {823--848},
volume = {22},
journal = {{VLDB} J.},
year = {2013}
}
@inproceedings{Mozafari:2017:AQE:3035918.3056098,
author = {Mozafari, Barzan},
booktitle = {{SIGMOD}},
title = {Approximate Query Engines: Commercial Challenges and Research Opportunities},
doi = {10.1145/3035918.3056098},
isbn = {978-1-4503-4197-4},
location = {Chicago, Illinois, USA},
pages = {521--524},
acmid = {3056098},
numpages = {4},
year = {2017}
}
@article{ilyas08survey,
author = {Ilyas, Ihab F and Beskales, George and Soliman, Mohamed A},
title = {A survey of top-$k$ query processing techniques in relational database systems},
doi = {10.1145/1391729.1391730},
number = {4},
pages = {11},
volume = {40},
journal = {ACM Computing Surveys},
year = {2008}
}
@inproceedings{kumar15ml,
author = {Kumar, Arun and Naughton, Jeffrey and Patel, Jignesh M},
booktitle = {SIGMOD},
title = {Learning generalized linear models over normalized data},
doi = {10.1145/2723372.2723713},
pages = {1969--1984},
year = {2015}
}
@inproceedings{schleich16ml,
author = {Schleich, Maximilian and Olteanu, Dan and Ciucanu, Radu},
booktitle = {{SIGMOD}},
title = {Learning linear regression models over factorized joins},
doi = {10.1145/2882903.2882939},
pages = {3--18},
year = {2016}
}
@article{DBLP:journals/tocl/DurandG07,
author = {Arnaud Durand and Etienne Grandjean},
title = {First-order queries on structures of bounded degree are computable with constant delay},
doi = {10.1145/1276920.1276923},
number = {4},
pages = {21},
volume = {8},
journal = {{ACM} TCL},
year = {2007}
}
@inproceedings{nepal99ta,
author = {Nepal, Surya and Ramakrishna, M. V.},
booktitle = {ICDE},
title = {Query processing issues in image (multimedia) databases},
doi = {10.1109/ICDE.1999.754894},
pages = {22--29},
year = {1999}
}
@article{khamis17juggling,
author = {Khamis, Mahmoud Abo and Ngo, Hung Q and Rudra, Atri},
title = {Juggling functions inside a database},
doi = {10.1145/3093754.3093757},
number = {1},
pages = {6--13},
volume = {46},
journal = {SIGMOD Record},
publisher = {ACM New York, NY, USA},
year = {2017}
}
@article{gottlob03width,
author = {Gottlob, Georg and Leone, Nicola and Scarcello, Francesco},
title = {Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width},
doi = {10.1145/375551.375579},
number = {4},
pages = {775--808},
volume = {66},
journal = {Journal of Computer and System Sciences},
publisher = {Elsevier},
year = {2003}
}
@inproceedings{yang2018any,
author = {Yang, Xiaofeng and Ajwani, Deepak and Gatterbauer, Wolfgang and Nicholson, Patrick K and Riedewald, Mirek and Sala, Alessandra},
booktitle = {WWW},
title = {Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs},
doi = {10.1145/3178876.3186115},
pages = {489--498},
year = {2018}
}
@inproceedings{kara19triangles,
author = {Ahmet Kara and Hung Q. Ngo and Milos Nikolic and Dan Olteanu and Haozhe Zhang},
booktitle = {ICDT},
title = {Counting Triangles under Updates in Worst-Case Optimal Time},
doi = {10.4230/LIPIcs.ICDT.2019.4},
pages = {4:1--4:18},
year = {2019}
}
@inproceedings{schnaitter08pbrj,
author = {Schnaitter, Karl and Polyzotis, Neoklis},
booktitle = {PODS},
title = {Evaluating rank joins with optimal cost},
doi = {10.1145/1376916.1376924},
pages = {43--52},
year = {2008}
}
@article{idris20dynamic_theta,
author = {Idris, Muhammad and Ugarte, Mart{\'\i}n and Vansummeren, Stijn and Voigt, Hannes and Lehner, Wolfgang},
title = {General dynamic Yannakakis: conjunctive queries with theta joins under updates},
doi = {10.1007/s00778-019-00590-9},
pages = {619--653},
volume = {29},
journal = {{VLDB} J.},
publisher = {Springer},
year = {2020}
}
@article{Ngo:2014:SSB:2590989.2590991,
author = {Ngo, Hung Q and R{\'e}, Christopher and Rudra, Atri},
title = {Skew Strikes Back: New Developments in the Theory of Join Algorithms},
doi = {10.1145/2590989.2590991},
issn = {0163-5808},
number = {4},
pages = {5--16},
volume = {42},
acmid = {2590991},
address = {New York, NY, USA},
journal = {SIGMOD Rec.},
numpages = {12},
publisher = {ACM},
year = {2014}
}
@inproceedings{kalinsky20graph,
author = {Kalinsky, Oren and Kimelfeld, Benny and Etsion, Yoav},
booktitle = {ASPLOS},
title = {The TrieJax Architecture: Accelerating Graph Operations Through Relational Joins},
doi = {10.1145/3373376.3378524},
pages = {1217--1231},
numpages = {15},
year = {2020}
}
@inproceedings{GottlobGLS:2016,
author = {Gottlob, Georg and Greco, Gianluigi and Leone, Nicola and Scarcello, Francesco},
booktitle = {PODS},
title = {Hypertree Decompositions: Questions and Answers},
doi = {10.1145/2902251.2902309},
isbn = {978-1-4503-4191-2},
pages = {57--74},
acmid = {2902309},
numpages = {18},
year = {2016}
}
@inproceedings{guntzer00qcombine,
author = {G{\"u}ntzer, Ulrich and Balke, Wolf-Tilo and Kie{\ss}ling, Werner},
booktitle = {VLDB},
title = {Optimizing multi-feature queries for image databases},
pages = {419--428},
url = {https://dl.acm.org/doi/10.5555/645926.671875},
year = {2000}
}
@article{segoufin15constenum,
author = {Segoufin, Luc},
title = {Constant Delay Enumeration for Conjunctive Queries.},
doi = {10.1145/2783888.2783894},
number = {1},
pages = {10--17},
volume = {44},
journal = {SIGMOD record},
year = {2015}
}
@inproceedings{finger09frpa,
author = {Finger, Jonathan and Polyzotis, Neoklis},
booktitle = {SIGMOD},
title = {Robust and efficient algorithms for rank join evaluation},
doi = {10.1145/1559845.1559890},
pages = {415--428},
year = {2009}
}
@article{GottlobLS:2002,
author = {Georg Gottlob and Nicola Leone and Francesco Scarcello},
title = {Hypertree Decompositions and Tractable Queries},
doi = {https://doi.org/10.1006/jcss.2001.1809},
issn = {0022-0000},
number = {3},
pages = {579 - 627},
volume = {64},
journal = {Journal of Computer and System Sciences},
year = {2002}
}
@article{Zaimag96,
author = {Shlomo Zilberstein},
title = {Using Anytime Algorithms in Intelligent Systems},
number = {3},
pages = {73-83},
url = {http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.html},
volume = {17},
journal = {AI Magazine},
year = {1996}
}
@inproceedings{KimelfeldS2006,
author = {Kimelfeld, Benny and Sagiv, Yehoshua},
booktitle = {International Workshop on Next Generation Information Technologies and Systems (NGITS)},
title = {Incrementally Computing Ordered Answers of Acyclic Conjunctive Queries},
doi = {10.1007/11780991_13},
isbn = {978-3-540-35473-4},
pages = {141--152},
year = {2006}
}
@article{mouratidis17topk,
author = {Mouratidis, Kyriakos},
title = {Geometric Approaches for Top-k Queries},
doi = {10.14778/3137765.3137826},
issn = {2150-8097},
number = {12},
pages = {1985--1987},
volume = {10},
journal = {PVLDB.},
numpages = {3},
publisher = {VLDB Endowment},
year = {2017}
}
@article{martins01kshortest,
author = {Martins, Ernesto de Queir{\'o}s Vieira and Pascoal, Marta Madalena Braz and Santos, Jos{\'e} Lu{\'\i}s Esteves},
title = {A new improvement for a K shortest paths algorithm},
number = {1},
pages = {47--60},
url = {http://apdio.pt/documents/10180/15407/IOvol21n1.pdf},
volume = {21},
journal = {Investiga{\c{c}}{\~a}o Operacional},
publisher = {APDIO-Associa{\c{c}}{\~a}o Portuguesa de Investiga{\c{c}}{\~a}o Operacional},
year = {2001}
}
@article{rahul19topk,
author = {Rahul, Saladi and Tao, Yufei},
title = {A Guide to Designing Top-k Indexes},
doi = {10.1145/3377330.3377332},
number = {2},
volume = {48},
journal = {SIGMOD Record},
year = {2019}
}
@inproceedings{deep18compressed,
author = {Deep, Shaleen and Koutris, Paraschos},
booktitle = {{PODS}},
title = {Compressed representations of conjunctive query results},
doi = {10.1145/3196959.3196979},
pages = {307--322},
year = {2018}
}
@inproceedings{olteanu12ftrees,
author = {Olteanu, Dan and Z{\'a}vodn{\`y}, Jakub},
booktitle = {ICDT},
title = {Factorised representations of query results: size bounds and readability},
doi = {10.1145/2274576.2274607},
pages = {285--298},
year = {2012}
}
@article{schnaitter09depth,
author = {Schnaitter, Karl and Spiegel, Joshua and Polyzotis, Neoklis},
title = {Depth estimation for ranking query optimization},
doi = {10.1007/s00778-008-0124-z},
number = {2},
pages = {521--542},
volume = {18},
journal = {{VLDB} J.},
publisher = {Springer},
year = {2009}
}
@inproceedings{khamis17panda,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q and Suciu, Dan},
booktitle = {PODS},
title = {What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?},
doi = {10.1145/3034786.3056105},
pages = {429--444},
year = {2017}
}
@inproceedings{khamis19negation,
author = {Mahmoud Abo Khamis and Hung Q. Ngo and Dan Olteanu and Dan Suciu},
booktitle = {ICDT},
title = {Boolean Tensor Decomposition for Conjunctive Queries with Negation},
doi = {10.4230/LIPIcs.ICDT.2019.21},
pages = {21:1--21:19},
year = {2019}
}
@article{eppstein1998finding,
author = {Eppstein, David},
title = {Finding the $k$ shortest paths},
doi = {10.1137/S0097539795290477},
number = {2},
pages = {652--673},
volume = {28},
journal = {{SIAM} J. Comput.},
publisher = {SIAM},
year = {1998}
}
@article{lin18topk,
author = {Lin, Chunbin and Lu, Jiaheng and Wei, Zhewei and Wang, Jianguo and Xiao, Xiaokui},
title = {Optimal algorithms for selecting top-k combinations of attributes: theory and applications},
doi = {10.1007/s00778-017-0485-2},
number = {1},
pages = {27--52},
volume = {27},
journal = {{VLDB} J.},
publisher = {Springer},
year = {2018}
}
@article{lawler72,
author = {Lawler, Eugene L},
title = {A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem},
doi = {10.1287/mnsc.18.7.401},
number = {7},
pages = {401--405},
volume = {18},
journal = {Management science},
publisher = {INFORMS},
year = {1972}
}
@article{bakibayev13fordering,
author = {Bakibayev, Nurzhan and Ko\v{c}isk\'{y}, Tom\'{a}\v{s} and Olteanu, Dan and Z\'{a}vodn\'{y}, Jakub},
title = {Aggregation and Ordering in Factorised Databases},
doi = {10.14778/2556549.2556579},
issn = {2150-8097},
number = {14},
pages = {1990--2001},
volume = {6},
journal = {PVLDB},
publisher = {VLDB Endowment},
year = {2013}
}
@inproceedings{fagin96fa,
author = {Fagin, Ronald},
booktitle = {PODS},
title = {Combining fuzzy information from multiple systems},
doi = {10.1145/237661.237715},
pages = {216--226},
year = {1996}
}
@article{Khamis:2016:JVG:3014437.2967101,
author = {Khamis, Mahmoud Abo and Ngo, Hung Q. and R{\'e}, Christopher and Rudra, Atri},
title = {Joins via Geometric Resolutions: Worst Case and Beyond},
doi = {10.1145/2967101},
issn = {0362-5915},
number = {4},
pages = {22:1--22:45},
volume = {41},
acmid = {2967101},
address = {New York, NY, USA},
journal = {TODS},
numpages = {45},
publisher = {ACM},
year = {2016}
}
@inproceedings{fagin98fa,
author = {Fagin, Ronald},
booktitle = {PODS},
title = {Fuzzy queries in multimedia database systems},
doi = {10.1145/275487.275488},
pages = {1--10},
year = {1998}
}
@article{DBLP:journals/jacm/BernsteinC81,
author = {Philip A. Bernstein and Dah{-}Ming W. Chiu},
title = {Using Semi-Joins to Solve Relational Queries},
doi = {10.1145/322234.322238},
number = {1},
pages = {25--40},
volume = {28},
journal = {J. {ACM}},
timestamp = {Tue, 06 Nov 2018 12:51:46 +0100},
year = {1981}
}
@article{olteanu16record,
author = {Olteanu, Dan and Schleich, Maximilian},
title = {Factorized databases},
doi = {10.1145/3003665.3003667},
number = {2},
volume = {45},
journal = {SIGMOD Record},
publisher = {Association for Computing Machinery},
year = {2016}
}
@inproceedings{khamis18ml,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q and Nguyen, XuanLong and Olteanu, Dan and Schleich, Maximilian},
booktitle = {PODS},
title = {In-database learning with sparse tensors},
doi = {10.1145/3196959.3196960},
pages = {325--340},
year = {2018}
}
@article{olteanu15dtrees,
author = {Olteanu, Dan and Z{\'a}vodn{\`y}, Jakub},
title = {Size bounds for factorised representations of query results},
doi = {10.1145/2656335},
number = {1},
pages = {2},
volume = {40},
journal = {TODS},
publisher = {ACM},
year = {2015}
}
@inproceedings{Boddy:1991,
author = {Boddy, Mark},
booktitle = {{AAAI}},
title = {Anytime Problem Solving Using Dynamic Programming},
isbn = {0-262-51059-6},
location = {Anaheim, California},
pages = {738--743},
url = {http://dl.acm.org/citation.cfm?id=1865756.1865791},
acmid = {1865791},
numpages = {6},
year = {1991}
}
@inproceedings{ngo14mine,
author = {Ngo, Hung Q and Nguyen, Dung T and Re, Christopher and Rudra, Atri},
booktitle = {PODS},
title = {Beyond worst-case analysis for joins with minesweeper},
doi = {10.1145/2594538.2594547},
pages = {234--245},
year = {2014}
}
@inproceedings{jimenez03shortest,
author = {Jim{\'e}nez, V{\'\i}ctor M and Marzal, Andr{\'e}s},
booktitle = {International Workshop on Experimental and Efficient Algorithms (WEA)},
title = {A lazy version of Eppstein's K shortest paths algorithm},
doi = {10.1007/3-540-44867-5_14},
organization = {Springer},
pages = {179--191},
year = {2003}
}
@inproceedings{Ngo:2012:WOJ:2213556.2213565,
author = {Ngo, Hung Q. and Porat, Ely and R{\'e}, Christopher and Rudra, Atri},
booktitle = {PODS},
title = {Worst-case Optimal Join Algorithms: [Extended Abstract]},
doi = {10.1145/2213556.2213565},
isbn = {978-1-4503-1248-6},
location = {Scottsdale, Arizona, USA},
pages = {37--48},
acmid = {2213565},
numpages = {12},
year = {2012}
}
@inproceedings{DBLP:conf/vldb/Yannakakis81,
author = {Mihalis Yannakakis},
booktitle = {VLDB},
title = {Algorithms for Acyclic Database Schemes},
pages = {82--94},
url = {https://dl.acm.org/doi/10.5555/1286831.1286840},
year = {1981}
}
@book{dpv08book,
author = {Dasgupta, Sanjoy and Papadimitriou, Christos H and Vazirani, Umesh Virkumar},
title = {Algorithms},
publisher = {McGraw-Hill Higher Education},
url = {https://dl.acm.org/doi/book/10.5555/1177299},
year = {2008}
}
@inproceedings{veldhuizen14leapfrog,
author = {Todd L. Veldhuizen},
booktitle = {ICDT},
title = {Triejoin: {A} Simple, Worst-Case Optimal Join Algorithm},
doi = {10.5441/002/icdt.2014.13},
pages = {96--106},
year = {2014}
}
@inproceedings{abo2016degree,
author = {Abo Khamis, Mahmoud and Ngo, Hung Q. and Suciu, Dan},
booktitle = {PODS},
title = {Computing join queries with functional dependencies},
doi = {10.1145/2902251.2902289},
pages = {327--342},
year = {2016}
}
@article{grohe14fhtw,
author = {Grohe, Martin and Marx, D{\'a}niel},
title = {Constraint solving via fractional edge covers},
doi = {10.1145/2636918},
number = {1},
pages = {4},
volume = {11},
journal = {ACM TALG},
publisher = {Acm},
year = {2014}
}
@inproceedings{bagan07constenum,
author = {Bagan, Guillaume and Durand, Arnaud and Grandjean, Etienne},
booktitle = {International Workshop on Computer Science Logic (CSL)},
title = {On acyclic conjunctive queries and constant delay enumeration},
doi = {10.1007/978-3-540-74915-8\_18},
pages = {208--222},
year = {2007}
}
@article{mamoulis07lara,
author = {Mamoulis, Nikos and Yiu, Man Lung and Cheng, Kit Hung and Cheung, David W},
title = {Efficient top-$k$ aggregation of ranked inputs},
doi = {10.1145/1272743.1272749},
number = {3},
pages = {19},
volume = {32},
journal = {TODS},
publisher = {ACM},
year = {2007}
}
@article{bakibayev12fdb,
author = {Bakibayev, Nurzhan and Olteanu, Dan and Z\'{a}vodn\'{y}, Jakub},
title = {FDB: A Query Engine for Factorised Relational Databases},
doi = {10.14778/2350229.2350242},
issn = {2150-8097},
number = {11},
pages = {1232--1243},
volume = {5},
journal = {PVLDB},
publisher = {VLDB Endowment},
year = {2012}
}
@inproceedings{schleich19ml,
author = {Schleich, Maximilian and Olteanu, Dan and Abo-Khamis, Mahmoud and Ngo, Hung Q and Nguyen, XuanLong},
booktitle = {International Conference on Scalable Uncertainty Management (SUM)},
title = {Learning Models over Relational Data: A Brief Tutorial},
doi = {10.1007/978-3-030-35514-2_32},
pages = {423--432},
year = {2019}
}
@article{aberger17emptyheaded,
author = {Aberger, Christopher R and Lamb, Andrew and Tu, Susan and N{\"o}tzli, Andres and Olukotun, Kunle and R{\'e}, Christopher},
title = {Emptyheaded: A relational engine for graph processing},
doi = {10.1145/3129246},
number = {4},
pages = {1--44},
volume = {42},
journal = {TODS},
publisher = {ACM New York, NY, USA},
year = {2017}
}
@inproceedings{Kalinsky16wco,
author = {Oren Kalinsky and Yoav Etsion and Benny Kimelfeld},
booktitle = {EDBT},
title = {Flexible Caching in Trie Joins},
doi = {10.5441/002/edbt.2017.26},
pages = {282--293},
year = {2016}
}
@article{greco17greedy,
author = {Greco, Gianluigi and Scarcello, Francesco},
title = {Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems},
doi = {10.1016/j.ic.2016.11.004},
pages = {201--220},
volume = {252},
journal = {Inf. Comput.},
publisher = {Elsevier},
year = {2017}
}
@article{AGM,
author = {Atserias, Albert and Grohe, Martin and Marx, D{\'a}niel},
title = {Size Bounds and Query Plans for Relational Joins},
doi = {10.1137/110859440},
number = {4},
pages = {1737-1767},
volume = {42},
journal = {SIAM Journal on Computing},
year = {2013}
}
@article{olteanu16ml,
author = {Olteanu, Dan and Schleich, Maximilian},
title = {F: Regression Models over Factorized Views},
doi = {10.14778/3007263.3007312},
issn = {2150-8097},
number = {13},
pages = {1573--1576},
volume = {9},
journal = {PVLDB},
numpages = {4},
publisher = {VLDB Endowment},
year = {2016}
}
@inproceedings{DBLP:conf/sigmod/HeuvelIGGT19,
author = {Maarten Van den Heuvel and Peter Ivanov and Wolfgang Gatterbauer and Floris Geerts and Martin Theobald},
booktitle = {{SIGMOD}},
title = {Anytime Approximation in Probabilistic Databases via Scaled Dissociations},
doi = {10.1145/3299869.3319900},
pages = {1295--1312},
timestamp = {Sat, 22 Jun 2019 17:10:04 +0200},
year = {2019}
}
@inbook{eppstein16kbest,
author = {Eppstein, David},
booktitle = {Encyclopedia of Algorithms},
title = {k-Best Enumeration},
doi = {10.1007/978-1-4939-2864-4_733},
editor = {Kao, Ming-Yang},
isbn = {978-1-4939-2864-4},
pages = {1003--1006},
publisher = {Springer, Encyclopedia of Algorithms},
year = {2016}
}
@book{bertsekas05dp,
author = {Dimitri P. Bertsekas},
title = {Dynamic Programming and Optimal Control},
edition = {3rd},
publisher = {Athena Scientific},
url = {http://www.athenasc.com/dpbook.html},
volume = {I},
year = {2005}
}
@article{dreyfus69shortest,
author = {Dreyfus, Stuart E},
title = {An appraisal of some shortest-path algorithms},
doi = {https://doi.org/10.1287/opre.17.3.395},
number = {3},
pages = {395--412},
volume = {17},
journal = {Operations research},
publisher = {INFORMS},
year = {1969}
}
@article{fagin03,
author = {Fagin, Ronald and Lotem, Amnon and Naor, Moni},
title = {Optimal aggregation algorithms for middleware},
doi = {10.1016/S0022-0000(03)00026-6},
number = {4},
pages = {614--656},
volume = {66},
journal = {Journal of Computer and System Sciences},
year = {2003}
}
@article{ilyas06rank,
author = {Ilyas, Ihab F. and Aref, Walid G. and Elmagarmid, Ahmed K. and Elmongui, Hicham G. and Shah, Rahul and Vitter, Jeffrey Scott},
title = {Adaptive Rank-Aware Query Optimization in Relational Databases},
doi = {10.1145/1189769.1189772},
number = {4},
pages = {1257--1304},
volume = {31},
address = {New York, NY, USA},
journal = {TODS},
numpages = {48},
publisher = {Association for Computing Machinery},
year = {2006}
}
@article{wu10topk,
author = {Wu, Minji and Berti-Equille, Laure and Marian, Am{\'e}lie and Procopiuc, Cecilia M and Srivastava, Divesh},
title = {Processing top-k join queries},
doi = {10.14778/1920841.1920951},
number = {1},
pages = {860--870},
volume = {3},
journal = {PVLDB},
publisher = {VLDB Endowment},
year = {2010}
}
@inproceedings{YangRLG18:anyKexploreDB,
author = {Yang, Xiaofeng and Riedewald, Mirek and Li, Rundong and Gatterbauer, Wolfgang},
booktitle = {International Workshop on Exploratory Search in Databases and the Web (ExploreDB)},
title = {Any-k Algorithms for Exploratory Analysis with Conjunctive Queries},
doi = {10.1145/3214708.3214711},
isbn = {9781450358477},
pages = {1--3},
numpages = {3},
year = {2018}
}
@article{DBLP:journals/jcss/GottlobGS18,
author = {Georg Gottlob and Gianluigi Greco and Francesco Scarcello},
title = {Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms},
doi = {10.1016/j.jcss.2017.11.005},
pages = {11--40},
volume = {94},
journal = {Journal of Computer and System Sciences},
year = {2018}
}
@inproceedings{khamis18acdc,
author = {Khamis, Mahmoud Abo and Ngo, Hung Q and Nguyen, XuanLong and Olteanu, Dan and Schleich, Maximilian},
booktitle = {Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning (DEEM)},
title = {AC/DC: in-database learning thunderstruck},
doi = {10.1145/3209889.3209896},
pages = {1--10},
year = {2018}
}
@inproceedings{jimenez99shortest,
author = {Jim{\'e}nez, V{\'\i}ctor M and Marzal, Andr{\'e}s},
booktitle = {International Workshop on Algorithm Engineering (WAE)},
title = {Computing the k shortest paths: A new algorithm and an experimental comparison},
doi = {10.1007/3-540-48318-7_4},
organization = {Springer},
pages = {15--29},
year = {1999}
}
@inproceedings{DBLP:conf/cp/GrecoS11,
author = {Gianluigi Greco and Francesco Scarcello},
booktitle = {International Conference on Principles and Practice of Constraint Programming (CP)},
title = {Structural Tractability of Constraint Optimization},
doi = {10.1007/978-3-642-23786-7\_27},
pages = {340--355},
timestamp = {Tue, 14 May 2019 10:00:45 +0200},
year = {2011}
}
@article{deep19,
author = {Shaleen Deep and Paraschos Koutris},
title = {Ranked Enumeration of Conjunctive Query Results},
url = {http://arxiv.org/abs/1902.02698},
volume = {abs/1902.02698},
archiveprefix = {arXiv},
date-modified = {2020-03-29 23:44:37 -0400},
journal = {CoRR},
timestamp = {Tue, 21 May 2019 18:03:37 +0200},
year = {2019}
}
@article{gottlob09generalized,
author = {Gottlob, Georg and Mikl{\'o}s, Zolt{\'a}n and Schwentick, Thomas},
title = {Generalized hypertree decompositions: NP-hardness and tractable variants},
doi = {10.1145/1568318.1568320},
number = {6},
pages = {30},
volume = {56},
journal = {J. {ACM}},
publisher = {ACM},
year = {2009}
}
@article{idris19dynamic,
author = {Idris, Muhammad and Ugarte, Mart{\'\i}n and Vansummeren, Stijn and Voigt, Hannes and Lehner, Wolfgang},
title = {Efficient Query Processing for Dynamically Changing Datasets},
doi = {10.1145/3371316.3371325},
number = {1},
pages = {33--40},
volume = {48},
journal = {SIGMOD Record},
publisher = {ACM New York, NY, USA},
year = {2019}
}
@article{gottlob12fds,
author = {Gottlob, Georg and Lee, Stephanie Tien and Valiant, Gregory and Valiant, Paul},
title = {Size and treewidth bounds for conjunctive queries},
doi = {10.1145/2220357.2220363},
number = {3},
pages = {1--35},
volume = {59},
journal = {J. {ACM}},
publisher = {ACM New York, NY, USA},
year = {2012}
}
@book{Cormen:2009dp,
author = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford},
title = {Introduction to Algorithms},
edition = {3rd},
isbn = {0262033844, 9780262033848},
publisher = {The MIT Press},
url = {https://dl.acm.org/doi/book/10.5555/1614191},
year = {2009}
}
@article{bellman60kbest,
author = {Bellman, Richard and Kalaba, Robert},
title = {On k th best policies},
doi = {10.1137/0108044},
number = {4},
pages = {582--588},
volume = {8},
journal = {Journal of the Society for Industrial and Applied Mathematics},
publisher = {SIAM},
year = {1960}
}
@article{ilyas04,
author = {Ilyas, Ihab F and Aref, Walid G and Elmagarmid, Ahmed K},
title = {Supporting top-$k$ join queries in relational databases},
doi = {10.1007/s00778-004-0128-2},
number = {3},
pages = {207--221},
volume = {13},
journal = {{VLDB} J.},
year = {2004}
}
@inproceedings{ngo18open,
author = {Ngo, Hung Q},
booktitle = {PODS},
title = {Worst-case optimal join algorithms: Techniques, results, and open problems},
doi = {10.1145/3196959.3196990},
pages = {111--124},
year = {2018}
}
@article{murty1968,
author = {Murty, Katta G.},
title = {An Algorithm for Ranking all the Assignments in Order of Increasing Cost},
doi = {10.1287/opre.16.3.682},
number = {3},
pages = {682-687},
volume = {16},
journal = {Operations Research},
year = {1968}
}
@article{Marx:2013:THP:2555516.2535926,
author = {Marx, D\'{a}niel},
title = {Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries},
doi = {10.1145/2535926},
issn = {0004-5411},
number = {6},
pages = {42:1--42:51},
volume = {60},
acmid = {2535926},
address = {New York, NY, USA},
articleno = {42},
journal = {J. ACM},
numpages = {51},
publisher = {ACM},
year = {2013}
}
This file was generated by bibtex2html 1.95.