| [1] | Michel Gondran and Michel Minoux. Graphs, Dioids and Semirings: New Models and Algorithms (Operations Research/Computer Science Interfaces Series). Springer, 2008. [ bib | DOI ] |
| [2] | Mehryar Mohri. Semiring frameworks and algorithms for shortest-distance problems. J. Autom. Lang. Comb., 7(3):321–350, Jan 2002. [ bib | http ] |
| [3] | S. M. Aji and R. J. McEliece. The generalized distributive law. IEEE Transactions on Information Theory, 46(2):325-343, 2000. [ bib | DOI ] |
| [4] | N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, Mar 1997. [ bib | DOI ] |
| [5] | Zhen Zhang, Seung-won Hwang, Kevin Chen-Chuan Chang, Min Wang, Christian A. Lang, and Yuan-chi Chang. Boolean + ranking: Querying a database by k-constrained optimization. In SIGMOD, page 359–370, 2006. [ bib | DOI ] |
| [6] | Gautam Das, Dimitrios Gunopulos, Nick Koudas, and Dimitris Tsirogiannis. Answering top-k queries using views. In VLDB, page 451–462, 2006. [ bib | .pdf ] |
| [7] | Vagelis Hristidis, Nick Koudas, and Yannis Papakonstantinou. Prefer: A system for the efficient execution of multi-parametric ranked queries. In SIGMOD, page 259–270, 2001. [ bib | DOI ] |
| [8] | Yuan-Chi Chang, Lawrence Bergman, Vittorio Castelli, Chung-Sheng Li, Ming-Ling Lo, and John R. Smith. The onion technique: Indexing for linear optimization queries. In SIGMOD, page 391–402, 2000. [ bib | DOI ] |
| [9] | Panayiotis Tsaparas, Themistoklis Palpanas, Yannis Kotidis, Nick Koudas, and Divesh Srivastava. Ranked join indices. In ICDE, pages 277-288, 2003. [ bib | DOI ] |
| [10] | Nicolas Bruno, Luis Gravano, and Amelie Marian. Evaluating top-k queries over web-accessible databases. In ICDE, pages 369-380, 2002. [ bib | DOI ] |
| [11] | H. Bast, Debapriyo Majumdar, Ralf Schenkel, Martin Theobald, and Gerhard Weikum. IO-top-k: Index-access optimized top-k query processing. In VLDB, pages 475-486, 2006. [ bib | http ] |
| [12] | Nikolaos Tziavelis, Deepak Ajwani, Wolfgang Gatterbauer, Mirek Riedewald, and Xiaofeng Yang. Optimal algorithms for ranked enumeration of answers to full conjunctive queries. PVLDB, 13(9):1582-1597, 2020. [ bib | DOI ] |
| [13] | Ronald Fagin. Combining fuzzy information from multiple systems. Journal of Computer and System Sciences, 58(1):83-99, 1999. [ bib | DOI ] |
| [14] | Lijun Chang, Xuemin Lin, Wenjie Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. Optimal enumeration: Efficient top-k tree matching. PVLDB, 8(5):533-544, 2015. [ bib | DOI ] |
| [15] | Gonzalo Navarro, Juan L Reutter, and Javiel Rojas-Ledesma. Optimal joins using compact data structures. In ICDT, 2020. [ bib | http ] |
| [16] | Hung Q Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms. J. ACM, 65(3):16, 2018. [ bib | DOI ] |
| [17] | Mahmoud Abo Khamis, Hung Q Ngo, and Atri Rudra. Faq: questions asked frequently. In PODS, pages 13-28, 2016. [ bib | DOI ] |
| [18] | Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In PODS, pages 303-318, 2017. [ bib | DOI ] |
| [19] | Neil Robertson and P.D Seymour. Graph minors. ii. algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309 - 322, 1986. [ bib | DOI ] |
| [20] | Aidan Hogan, Cristian Riveros, Carlos Rojas, and Adrián Soto. A worst-case optimal join algorithm for sparql. In ISWC, pages 258-275, 2019. [ bib | DOI ] |
| [21] | Mahmoud Abo Khamis, Ryan R. Curtin, Benjamin Moseley, Hung Q. Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. On functional aggregate queries with additive inequalities. In PODS, pages 414-431, 2019. [ bib | DOI ] |
| [22] | Apostol Natsev, Yuan-Chi Chang, John R Smith, Chung-Sheng Li, and Jeffrey Scott Vitter. Supporting incremental join queries on ranked inputs. In VLDB, pages 281-290, 2001. [ bib | .pdf ] |
| [23] | Gianluigi Greco and Francesco Scarcello. The power of local consistency in conjunctive queries and constraint satisfaction problems. SIAM Journal on Computing, 46(3):1111-1145, 2017. [ bib | DOI ] |
| [24] | Walter Hoffman and Richard Pavley. A method for the solution of the nth best path problem. J. ACM, 6(4):506-514, 1959. [ bib | DOI ] |
| [25] | Rina Dechter. From local to global consistency. Artif. Intell., 55(1):87-108, 1992. [ bib | DOI ] |
| [26] | Manas Joglekar and Christopher Ré. It's all a matter of degree. Theory of Computing Systems, 62(4):810-853, 2018. [ bib | DOI ] |
| [27] | Robert Fink, Jiewen Huang, and Dan Olteanu. Anytime approximation in probabilistic databases. VLDB J., 22(6):823-848, 2013. [ bib | DOI ] |
| [28] | Barzan Mozafari. Approximate query engines: Commercial challenges and research opportunities. In SIGMOD, pages 521-524, 2017. [ bib | DOI ] |
| [29] | Ihab F Ilyas, George Beskales, and Mohamed A Soliman. A survey of top-k query processing techniques in relational database systems. ACM Computing Surveys, 40(4):11, 2008. [ bib | DOI ] |
| [30] | Arun Kumar, Jeffrey Naughton, and Jignesh M Patel. Learning generalized linear models over normalized data. In SIGMOD, pages 1969-1984, 2015. [ bib | DOI ] |
| [31] | Maximilian Schleich, Dan Olteanu, and Radu Ciucanu. Learning linear regression models over factorized joins. In SIGMOD, pages 3-18, 2016. [ bib | DOI ] |
| [32] | Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. ACM TCL, 8(4):21, 2007. [ bib | DOI ] |
| [33] | Surya Nepal and M. V. Ramakrishna. Query processing issues in image (multimedia) databases. In ICDE, pages 22-29, 1999. [ bib | DOI ] |
| [34] | Mahmoud Abo Khamis, Hung Q Ngo, and Atri Rudra. Juggling functions inside a database. SIGMOD Record, 46(1):6-13, 2017. [ bib | DOI ] |
| [35] | Georg Gottlob, Nicola Leone, and Francesco Scarcello. Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. Journal of Computer and System Sciences, 66(4):775-808, 2003. [ bib | DOI ] |
| [36] | Xiaofeng Yang, Deepak Ajwani, Wolfgang Gatterbauer, Patrick K Nicholson, Mirek Riedewald, and Alessandra Sala. Any-k: Anytime top-k tree pattern retrieval in labeled graphs. In WWW, pages 489-498, 2018. [ bib | DOI ] |
| [37] | Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. Counting triangles under updates in worst-case optimal time. In ICDT, pages 4:1-4:18, 2019. [ bib | DOI ] |
| [38] | Karl Schnaitter and Neoklis Polyzotis. Evaluating rank joins with optimal cost. In PODS, pages 43-52, 2008. [ bib | DOI ] |
| [39] | Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner. General dynamic yannakakis: conjunctive queries with theta joins under updates. VLDB J., 29:619-653, 2020. [ bib | DOI ] |
| [40] | Hung Q Ngo, Christopher Ré, and Atri Rudra. Skew strikes back: New developments in the theory of join algorithms. SIGMOD Rec., 42(4):5-16, 2014. [ bib | DOI ] |
| [41] | Oren Kalinsky, Benny Kimelfeld, and Yoav Etsion. The triejax architecture: Accelerating graph operations through relational joins. In ASPLOS, pages 1217-1231, 2020. [ bib | DOI ] |
| [42] | Georg Gottlob, Gianluigi Greco, Nicola Leone, and Francesco Scarcello. Hypertree decompositions: Questions and answers. In PODS, pages 57-74, 2016. [ bib | DOI ] |
| [43] | Ulrich Güntzer, Wolf-Tilo Balke, and Werner Kießling. Optimizing multi-feature queries for image databases. In VLDB, pages 419-428, 2000. [ bib | http ] |
| [44] | Luc Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD record, 44(1):10-17, 2015. [ bib | DOI ] |
| [45] | Jonathan Finger and Neoklis Polyzotis. Robust and efficient algorithms for rank join evaluation. In SIGMOD, pages 415-428, 2009. [ bib | DOI ] |
| [46] | Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3):579 - 627, 2002. [ bib | DOI ] |
| [47] | Shlomo Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17(3):73-83, 1996. [ bib | .html ] |
| [48] | Benny Kimelfeld and Yehoshua Sagiv. Incrementally computing ordered answers of acyclic conjunctive queries. In International Workshop on Next Generation Information Technologies and Systems (NGITS), pages 141-152, 2006. [ bib | DOI ] |
| [49] | Kyriakos Mouratidis. Geometric approaches for top-k queries. PVLDB., 10(12):1985-1987, 2017. [ bib | DOI ] |
| [50] | Ernesto de Queirós Vieira Martins, Marta Madalena Braz Pascoal, and José Luís Esteves Santos. A new improvement for a k shortest paths algorithm. Investigação Operacional, 21(1):47-60, 2001. [ bib | .pdf ] |
| [51] | Saladi Rahul and Yufei Tao. A guide to designing top-k indexes. SIGMOD Record, 48(2), 2019. [ bib | DOI ] |
| [52] | Shaleen Deep and Paraschos Koutris. Compressed representations of conjunctive query results. In PODS, pages 307-322, 2018. [ bib | DOI ] |
| [53] | Dan Olteanu and Jakub Závodny. Factorised representations of query results: size bounds and readability. In ICDT, pages 285-298, 2012. [ bib | DOI ] |
| [54] | Karl Schnaitter, Joshua Spiegel, and Neoklis Polyzotis. Depth estimation for ranking query optimization. VLDB J., 18(2):521-542, 2009. [ bib | DOI ] |
| [55] | Mahmoud Abo Khamis, Hung Q Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In PODS, pages 429-444, 2017. [ bib | DOI ] |
| [56] | Mahmoud Abo Khamis, Hung Q. Ngo, Dan Olteanu, and Dan Suciu. Boolean tensor decomposition for conjunctive queries with negation. In ICDT, pages 21:1-21:19, 2019. [ bib | DOI ] |
| [57] | David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28(2):652-673, 1998. [ bib | DOI ] |
| [58] | Chunbin Lin, Jiaheng Lu, Zhewei Wei, Jianguo Wang, and Xiaokui Xiao. Optimal algorithms for selecting top-k combinations of attributes: theory and applications. VLDB J., 27(1):27-52, 2018. [ bib | DOI ] |
| [59] | Eugene L Lawler. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management science, 18(7):401-405, 1972. [ bib | DOI ] |
| [60] | Nurzhan Bakibayev, Tomáš Kočiský, Dan Olteanu, and Jakub Závodný. Aggregation and ordering in factorised databases. PVLDB, 6(14):1990-2001, 2013. [ bib | DOI ] |
| [61] | Ronald Fagin. Combining fuzzy information from multiple systems. In PODS, pages 216-226, 1996. [ bib | DOI ] |
| [62] | Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Joins via geometric resolutions: Worst case and beyond. TODS, 41(4):22:1-22:45, 2016. [ bib | DOI ] |
| [63] | Ronald Fagin. Fuzzy queries in multimedia database systems. In PODS, pages 1-10, 1998. [ bib | DOI ] |
| [64] | Philip A. Bernstein and Dah-Ming W. Chiu. Using semi-joins to solve relational queries. J. ACM, 28(1):25-40, 1981. [ bib | DOI ] |
| [65] | Dan Olteanu and Maximilian Schleich. Factorized databases. SIGMOD Record, 45(2), 2016. [ bib | DOI ] |
| [66] | Mahmoud Abo Khamis, Hung Q Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. In-database learning with sparse tensors. In PODS, pages 325-340, 2018. [ bib | DOI ] |
| [67] | Dan Olteanu and Jakub Závodny. Size bounds for factorised representations of query results. TODS, 40(1):2, 2015. [ bib | DOI ] |
| [68] | Mark Boddy. Anytime problem solving using dynamic programming. In AAAI, pages 738-743, 1991. [ bib | http ] |
| [69] | Hung Q Ngo, Dung T Nguyen, Christopher Re, and Atri Rudra. Beyond worst-case analysis for joins with minesweeper. In PODS, pages 234-245, 2014. [ bib | DOI ] |
| [70] | Víctor M Jiménez and Andrés Marzal. A lazy version of eppstein's k shortest paths algorithm. In International Workshop on Experimental and Efficient Algorithms (WEA), pages 179-191. Springer, 2003. [ bib | DOI ] |
| [71] | Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. Worst-case optimal join algorithms: [extended abstract]. In PODS, pages 37-48, 2012. [ bib | DOI ] |
| [72] | Mihalis Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82-94, 1981. [ bib | http ] |
| [73] | Sanjoy Dasgupta, Christos H Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. McGraw-Hill Higher Education, 2008. [ bib | http ] |
| [74] | Todd L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT, pages 96-106, 2014. [ bib | DOI ] |
| [75] | Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. Computing join queries with functional dependencies. In PODS, pages 327-342, 2016. [ bib | DOI ] |
| [76] | Martin Grohe and Dániel Marx. Constraint solving via fractional edge covers. ACM TALG, 11(1):4, 2014. [ bib | DOI ] |
| [77] | Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In International Workshop on Computer Science Logic (CSL), pages 208-222, 2007. [ bib | DOI ] |
| [78] | Nikos Mamoulis, Man Lung Yiu, Kit Hung Cheng, and David W Cheung. Efficient top-k aggregation of ranked inputs. TODS, 32(3):19, 2007. [ bib | DOI ] |
| [79] | Nurzhan Bakibayev, Dan Olteanu, and Jakub Závodný. Fdb: A query engine for factorised relational databases. PVLDB, 5(11):1232-1243, 2012. [ bib | DOI ] |
| [80] | Maximilian Schleich, Dan Olteanu, Mahmoud Abo-Khamis, Hung Q Ngo, and XuanLong Nguyen. Learning models over relational data: A brief tutorial. In International Conference on Scalable Uncertainty Management (SUM), pages 423-432, 2019. [ bib | DOI ] |
| [81] | Christopher R Aberger, Andrew Lamb, Susan Tu, Andres Nötzli, Kunle Olukotun, and Christopher Ré. Emptyheaded: A relational engine for graph processing. TODS, 42(4):1-44, 2017. [ bib | DOI ] |
| [82] | Oren Kalinsky, Yoav Etsion, and Benny Kimelfeld. Flexible caching in trie joins. In EDBT, pages 282-293, 2016. [ bib | DOI ] |
| [83] | Gianluigi Greco and Francesco Scarcello. Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems. Inf. Comput., 252:201-220, 2017. [ bib | DOI ] |
| [84] | Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737-1767, 2013. [ bib | DOI ] |
| [85] | Dan Olteanu and Maximilian Schleich. F: Regression models over factorized views. PVLDB, 9(13):1573-1576, 2016. [ bib | DOI ] |
| [86] | Maarten Van den Heuvel, Peter Ivanov, Wolfgang Gatterbauer, Floris Geerts, and Martin Theobald. Anytime approximation in probabilistic databases via scaled dissociations. In SIGMOD, pages 1295-1312, 2019. [ bib | DOI ] |
| [87] | David Eppstein. k-Best Enumeration, pages 1003-1006. Springer, Encyclopedia of Algorithms, 2016. [ bib | DOI ] |
| [88] | Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, volume I. Athena Scientific, 3rd edition, 2005. [ bib | .html ] |
| [89] | Stuart E Dreyfus. An appraisal of some shortest-path algorithms. Operations research, 17(3):395-412, 1969. [ bib | DOI ] |
| [90] | Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences, 66(4):614-656, 2003. [ bib | DOI ] |
| [91] | Ihab F. Ilyas, Walid G. Aref, Ahmed K. Elmagarmid, Hicham G. Elmongui, Rahul Shah, and Jeffrey Scott Vitter. Adaptive rank-aware query optimization in relational databases. TODS, 31(4):1257-1304, 2006. [ bib | DOI ] |
| [92] | Minji Wu, Laure Berti-Equille, Amélie Marian, Cecilia M Procopiuc, and Divesh Srivastava. Processing top-k join queries. PVLDB, 3(1):860-870, 2010. [ bib | DOI ] |
| [93] | Xiaofeng Yang, Mirek Riedewald, Rundong Li, and Wolfgang Gatterbauer. Any-k algorithms for exploratory analysis with conjunctive queries. In International Workshop on Exploratory Search in Databases and the Web (ExploreDB), pages 1-3, 2018. [ bib | DOI ] |
| [94] | Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms. Journal of Computer and System Sciences, 94:11-40, 2018. [ bib | DOI ] |
| [95] | Mahmoud Abo Khamis, Hung Q Ngo, XuanLong Nguyen, Dan Olteanu, and Maximilian Schleich. Ac/dc: in-database learning thunderstruck. In Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning (DEEM), pages 1-10, 2018. [ bib | DOI ] |
| [96] | Víctor M Jiménez and Andrés Marzal. Computing the k shortest paths: A new algorithm and an experimental comparison. In International Workshop on Algorithm Engineering (WAE), pages 15-29. Springer, 1999. [ bib | DOI ] |
| [97] | Gianluigi Greco and Francesco Scarcello. Structural tractability of constraint optimization. In International Conference on Principles and Practice of Constraint Programming (CP), pages 340-355, 2011. [ bib | DOI ] |
| [98] | Shaleen Deep and Paraschos Koutris. Ranked enumeration of conjunctive query results. CoRR, abs/1902.02698, 2019. [ bib | http ] |
| [99] | Georg Gottlob, Zoltán Miklós, and Thomas Schwentick. Generalized hypertree decompositions: Np-hardness and tractable variants. J. ACM, 56(6):30, 2009. [ bib | DOI ] |
| [100] | Muhammad Idris, Martín Ugarte, Stijn Vansummeren, Hannes Voigt, and Wolfgang Lehner. Efficient query processing for dynamically changing datasets. SIGMOD Record, 48(1):33-40, 2019. [ bib | DOI ] |
| [101] | Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant. Size and treewidth bounds for conjunctive queries. J. ACM, 59(3):1-35, 2012. [ bib | DOI ] |
| [102] | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. [ bib | http ] |
| [103] | Richard Bellman and Robert Kalaba. On k th best policies. Journal of the Society for Industrial and Applied Mathematics, 8(4):582-588, 1960. [ bib | DOI ] |
| [104] | Ihab F Ilyas, Walid G Aref, and Ahmed K Elmagarmid. Supporting top-k join queries in relational databases. VLDB J., 13(3):207-221, 2004. [ bib | DOI ] |
| [105] | Hung Q Ngo. Worst-case optimal join algorithms: Techniques, results, and open problems. In PODS, pages 111-124, 2018. [ bib | DOI ] |
| [106] | Katta G. Murty. An algorithm for ranking all the assignments in order of increasing cost. Operations Research, 16(3):682-687, 1968. [ bib | DOI ] |
| [107] | Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60(6):42:1-42:51, 2013. [ bib | DOI ] |
This file was generated by bibtex2html 1.95.