text:
@inproceedings{10.1145/3375395.3387641,
author = {Grohe, Martin},
title = {Word2vec, Node2vec, Graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387641},
doi = {10.1145/3375395.3387641},
abstract = {Vector representations of graphs and relational structures, whether hand-crafted feature vectors or learned representations, enable us to apply standard data analysis and machine learning techniques to the structures. A wide range of methods for generating such embeddings have been studied in the machine learning and knowledge representation literature. However, vector embeddings have received relatively little attention from a theoretical point of view. Starting with a survey of embedding techniques that have been used in practice, in this paper we propose two theoretical approaches that we see as central for understanding the foundations of vector embeddings. We draw connections between the various approaches and suggest directions for future research.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {1–16},
numpages = {16},
keywords = {graph neural net, graph kernel, representation learning, weisfeiler leman, homomorphism, vector embedding},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387723,
author = {Gottlob, Georg and Van den Bussche, Jan and Van Gucht, Dirk},
title = {2020 ACM PODS Alberto O. Mendelzon Test-of-Time Award},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387723},
doi = {10.1145/3375395.3387723},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {17},
numpages = {1},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3389129,
author = {Suciu, Dan},
title = {Probabilistic Databases for All},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3389129},
doi = {10.1145/3375395.3389129},
abstract = {In probabilistic databases the data is uncertain and is modeled by a probability distribution. The central problem in probabilistic databases is query evaluation, which requires performing not only traditional data processing such as joins, projections, unions, but also probabilistic inference in order to compute the probability of each item in the answer. At their core, probabilistic databases are a proposal to integrate logic with probability theory. This paper accompanies a talk given as part of the Gems of PODS series, and describes several results in probabilistic databases, explaining their significance in the broader context of model counting, probabilistic inference, and Statistical Relational Models.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {19–31},
numpages = {13},
keywords = {model counting, knowledge compilation, query processing, probabilistic inference},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387970,
author = {Console, Marco and Guagliardo, Paolo and Libkin, Leonid and Toussaint, Etienne},
title = {Coping with Incomplete Data: Recent Advances},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387970},
doi = {10.1145/3375395.3387970},
abstract = {Handling incomplete data in a correct manner is a notoriously hard problem in databases. Theoretical approaches rely on the computationally hard notion of certain answers, while practical solutions rely on ad hoc query evaluation techniques based on three-valued logic. Can we find a middle ground, and produce correct answers efficiently?The paper surveys results of the last few years motivated by this question. We re-examine the notion of certainty itself, and show that it is much more varied than previously thought. We identify cases when certain answers can be computed efficiently and, short of that, provide deterministic and probabilistic approximation schemes for them. We look at the role of three-valued logic as used in SQL query evaluation, and discuss the correctness of the choice, as well as the necessity of such a logic for producing query answers.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {33–47},
numpages = {15},
keywords = {naive evaluation, certain answers, incomplete information, relational databases, approximate query answering, many-valued logics},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387643,
author = {Ben-Eliezer, Omri and Yogev, Eylon},
title = {The Adversarial Robustness of Sampling},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387643},
doi = {10.1145/3375395.3387643},
abstract = {Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet "representative" subset of the data. In this work, we investigate the robustness of sampling against adaptive adversarial attacks in a streaming setting: An adversary sends a stream of elements from a universe U to a sampling algorithm (e.g., Bernoulli sampling or reservoir sampling), with the goal of making the sample "very unrepresentative" of the underlying data stream. The adversary is fully adaptive in the sense that it knows the exact content of the sample at any given point along the stream, and can choose which element to send next accordingly, in an online manner. Well-known results in the static setting indicate that if the full stream is chosen in advance (non-adaptively), then a random sample of size Ω(d/ε2) is an ε-approximation of the full data with good probability, where d is the VC-dimension of the underlying set system (U, R). Does this sample size suffice for robustness against an adaptive adversary? The simplistic answer is negative : We demonstrate a set system where a constant sample size (corresponding to a VC-dimension of 1) suffices in the static setting, yet an adaptive adversary can make the sample very unrepresentative, as long as the sample size is (strongly) sublinear in the stream length, using a simple and easy-to-implement attack. However, this attack is "theoretical only", requiring the set system size to (essentially) be exponential in the stream length. This is not a coincidence: We show that in order to make the sampling algorithm robust against adaptive adversaries, the modification required is solely to replace the VC-dimension term d in the sample size with the cardinality term log |R|. That is, the Bernoulli and reservoir sampling algorithms with sample size Ω(log |R|/ε2) output a representative sample of the stream with good probability, even in the presence of an adaptive adversary. This nearly matches the bound imposed by the attack.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {49–62},
numpages = {14},
keywords = {adversarial model, ε-approximation, random sampling, streaming},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387658,
author = {Ben-Eliezer, Omri and Jayaram, Rajesh and Woodruff, David P. and Yogev, Eylon},
title = {A Framework for Adversarially Robust Streaming Algorithms},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387658},
doi = {10.1145/3375395.3387658},
abstract = {We investigate the adversarial robustness of streaming algorithms. In this context, an algorithm is considered robust if its performance guarantees hold even if the stream is chosen adaptively by an adversary that observes the outputs of the algorithm along the stream and can react in an online manner. While deterministic streaming algorithms are inherently robust, many central problems in the streaming literature do not admit sublinear-space deterministic algorithms; on the other hand, classical space-efficient randomized algorithms for these problems are generally not adversarially robust. This raises the natural question of whether there exist efficient adversarially robust (randomized) streaming algorithms for these problems. In this work, we show that the answer is positive for various important streaming problems in the insertion-only model, including distinct elements and more generally $F_p$-estimation, Fp-heavy hitters, entropy estimation, and others. For all of these problems, we develop adversarially robust (1+ε)-approximation algorithms whose required space matches that of the best known non-robust algorithms up to a poly(log n, 1/ε) multiplicative factor (and in some cases even up to a constant factor). Towards this end, we develop several generic tools allowing one to efficiently transform a non-robust streaming algorithm into a robust one in various scenarios.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {63–80},
numpages = {18},
keywords = {distinct elements, databases, frequency moments, heavy hitters, adversarial robustness, streaming algorithms},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387650,
author = {Cormode, Graham and Vesel\'{y}, Pavel},
title = {A Tight Lower Bound for Comparison-Based Quantile Summaries},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387650},
doi = {10.1145/3375395.3387650},
abstract = {Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a totally ordered universe. We study data structures, called quantile summaries, which keep track of all quantiles of a stream of items, up to an error of at most ε. That is, an ε-approximate quantile summary first processes a stream and then, given any quantile query 0\l{}e φ\l{}e 1, returns an item from the stream, which is a φ'-quantile for some φ' = φ +- ε. We focus on comparison-based quantile summaries that can only compare two items and are otherwise completely oblivious of the universe. The best such deterministic quantile summary to date, due to Greenwald and Khanna [6], stores at most O(1/ε ⋅ log ε N) items, where N is the number of items in the stream. We prove that this space bound is optimal by showing a matching lower bound. Our result thus rules out the possibility of constructing a deterministic comparison-based quantile summary in space f(ε)⋅ o(log N), for any function f that does not depend on N. As a corollary, we improve the lower bound for biased quantiles, which provide a stronger, relative-error guarantee of (1+-ε)⋅ φ, and for other related computational tasks.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {81–93},
numpages = {13},
keywords = {lower bounds, quantiles},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387645,
author = {Abo Khamis, Mahmoud and Kolaitis, Phokion G. and Ngo, Hung Q. and Suciu, Dan},
title = {Bag Query Containment and Information Theory},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387645},
doi = {10.1145/3375395.3387645},
abstract = {The query containment problem is a fundamental algorithmic problem in data management. While this problem is well understood under set semantics, it is by far less understood under bag semantics. In particular, it is a long-standing open question whether or not the conjunctive query containment problem under bag semantics is decidable. We unveil tight connections between information theory and the conjunctive query containment under bag semantics. These connections are established using information inequalities, which are considered to be the laws of information theory. Our first main result asserts that deciding the validity of a generalization of information inequalities is many-one equivalent to the restricted case of conjunctive query containment in which the containing query is acyclic; thus, either both these problems are decidable or both are undecidable. Our second main result identifies a new decidable case of the conjunctive query containment problem under bag semantics. Specifically, we give an exponential time algorithm for conjunctive query containment under bag semantics, provided the containing query is chordal and admits a simple junction tree.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {95–112},
numpages = {18},
keywords = {information theory, query containment, bag semantics, entropy},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387654,
author = {Koutris, Paraschos and Wijsen, Jef},
title = {First-Order Rewritability in Consistent Query Answering with Respect to Multiple Keys},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387654},
doi = {10.1145/3375395.3387654},
abstract = {We study consistent query answering with respect to key dependencies. Given a (possibly inconsistent) database instance and a set of key dependencies, a repair is an inclusion-maximal subinstance that satisfies all key dependencies. Consistent query answering for a Boolean query is the following problem: given a database instance as input, is the query true in every repair? In [Koutris and Wijsen, ICDT 2019], it was shown that for every self-join-free Boolean conjunctive query and set of key dependencies containing exactly one key dependency per relation name (also called the primary key), this problem is in FO, L-complete, or coNP-complete, and it is decidable which of the three cases applies. In this paper, we consider the more general case where a relation name can be associated with more than one key dependency. It is shown that in this more general setting, it remains decidable whether or not the above problem is in FO, for self-join-free Boolean conjunctive queries. Moreover, it is possible to effectively construct a first-order query that solves the problem whenever such a query exists.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {113–129},
numpages = {17},
keywords = {consistent query answering, conjunctive queries, database repairing, keys, first-order rewriting},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387661,
author = {Benedikt, Michael and Kikot, Stanislav and Ostropolski-Nalewaja, Piotr and Romero, Miguel},
title = {On Monotonic Determinacy and Rewritability for Recursive Queries and Views},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387661},
doi = {10.1145/3375395.3387661},
abstract = {A query Q is monotonically determined over a set of views if Q can be expressed as a monotonic function of the view image. In the case of relational algebra views and queries, monotonic determinacy coincides with rewritability as a union of conjunctive queries, and it is decidable in important special cases, such as for CQ views and queries. We investigate the situation for views and queries in the recursive query language Datalog. We give both positive and negative results about the ability to decide monotonic determinacy, and also about the co-incidence of monotonic determinacy with Datalog rewritability.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {131–148},
numpages = {18},
keywords = {datalog, monotone determinacy, rewriting},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387642,
author = {Monet, Mika\"{e}l},
title = {Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387642},
doi = {10.1145/3375395.3387642},
abstract = {We consider the problem of exact probabilistic inference for Union of Conjunctive Queries (UCQs) on tuple-independent databases. For this problem, two approaches currently coexist. In the extensional method, query evaluation is performed by exploiting the structure of the query, and relies heavily on the use of the inclusion--exclusion principle. In the intensional method, one first builds a representation of the lineage of the query in a tractable formalism of knowledge compilation. The chosen formalism should then ensure that the probability can be efficiently computed using simple disjointness and independence assumptions, without the need of performing inclusion--exclusion. The extensional approach has long been thought to be strictly more powerful than the intensional approach, the reason being that for some queries, the use of inclusion--exclusion seemed unavoidable. In this paper we introduce a new technique to construct lineage representations as deterministic decomposable circuits in polynomial time. We prove that this technique applies to a class of UCQs that had been conjectured to separate the complexity of the two approaches. In essence, we show that relying on the inclusion--exclusion formula can be avoided by using negation. This result brings back hope to prove that the intensional approach can handle all tractable UCQs.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {149–163},
numpages = {15},
keywords = {tuple-independent databases, deterministic decomposable boolean circuits, knowledge compilation, inclusion--exclusion principle},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387656,
author = {Arenas, Marcelo and Barcel\'{o}, Pablo and Monet, Mika\"{e}l},
title = {Counting Problems over Incomplete Databases},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387656},
doi = {10.1145/3375395.3387656},
abstract = {We study the complexity of various fundamental counting problems that arise in the context of incomplete databases, i.e., relational databases that can contain unknown values in the form of labeled nulls. Specifically, we assume that the domains of these unknown values are finite and, for a Boolean query q, we consider the following two problems: given as input an incomplete database D, (a) return the number of completions of D that satisfy q; or (b) return or the number of valuations of the nulls of D yielding a completion that satisfies q. We obtain dichotomies between #P-hardness and polynomial-time computability for these problems when q is a self-join-free conjunctive query, and study the impact on the complexity of the following two restrictions: (1) every null occurs at most once in D (what is called Codd tables); and (2) the domain of each null is the same. Roughly speaking, we show that counting completions is much harder than counting valuations (for instance, while the latter is always in #P, we prove that the former is not in #P under some widely believed theoretical complexity assumption). Moreover, we find that both (1) and (2) reduce the complexity of our problems. We also study the approximability of these problems and show that, while counting valuations always has a fully polynomial randomized approximation scheme, in most cases counting completions does not. Finally, we consider more expressive query languages and situate our problems with respect to known complexity classes.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {165–177},
numpages = {13},
keywords = {closed-world assumption, fpras, counting complexity, incomplete databases},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387666,
author = {Console, Marco and Hofer, Matthias and Libkin, Leonid},
title = {Queries with Arithmetic on Incomplete Databases},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387666},
doi = {10.1145/3375395.3387666},
abstract = {The standard notion of query answering over incomplete database is that of certain answers, guaranteeing correctness regardless of how incomplete data is interpreted. In majority of real-life databases, relations have numerical columns and queries use arithmetic and comparisons. Even though the notion of certain answers still applies, we explain that it becomes much more problematic in situations when missing data occurs in numerical columns.We propose a new general framework that allows us to assign a measure of certainty to query answers. We test it in the agnostic scenario where we do not have prior information about values of numerical attributes, similarly to the predominant approach in handling incomplete data which assumes that each null can be interpreted as an arbitrary value of the domain. The key technical challenge is the lack of a uniform distribution over the entire domain of numerical attributes, such as real numbers. We overcome this by associating the measure of certainty with the asymptotic behavior of volumes of some subsets of the Euclidean space. We show that this measure is well-defined, and describe approaches to computing and approximating it. While it can be computationally hard, or result in an irrational number, even for simple constraints, we produce polynomial-time randomized approximation schemes with multiplicative guarantees for conjunctive queries, and with additive guarantees for arbitrary first-order queries. We also describe a set of experimental results to confirm the feasibility of this approach.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {179–189},
numpages = {11},
keywords = {missing data, asymptotic behavior, approximate query answers, query answering, incomplete information, measure of certainty, numerical data, first-order queries},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387648,
author = {Aum\"{u}ller, Martin and Pagh, Rasmus and Silvestri, Francesco},
title = {Fair Near Neighbor Search: Independent Range Sampling in High Dimensions},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387648},
doi = {10.1145/3375395.3387648},
abstract = {Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. There are several variants of the similarity search problem, and one of the most relevant is the r-near neighbor (r-NN) problem: given a radius r>0 and a set of points S, construct a data structure that, for any given query point q, returns a point p within distance at most r from q. In this paper, we study the r-NN problem in the light of fairness. We consider fairness in the sense of equal opportunity: all points that are within distance r from the query should have the same probability to be returned. In the low-dimensional case, this problem was first studied by Hu, Qiao, and Tao (PODS 2014). Locality sensitive hashing (LSH), the theoretically strongest approach to similarity search in high dimensions, does not provide such a fairness guarantee. To address this, we propose efficient data structures for r-NN where all points in S that are near q have the same probability to be selected and returned by the query. Specifically, we first propose a black-box approach that, given any LSH scheme, constructs a data structure for uniformly sampling points in the neighborhood of a query. Then, we develop a data structure for fair similarity search under inner product that requires nearly-linear space and exploits locality sensitive filters. The paper concludes with an experimental evaluation that highlights (un)fairness in a recommendation setting on real-world datasets and discusses the inherent unfairness introduced by solving other variants of the problem.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {191–204},
numpages = {14},
keywords = {similarity search, sampling, locality sensitive hashing, fairness},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387649,
author = {Goswami, Mayank and Jacob, Riko and Pagh, Rasmus},
title = {On the I/O Complexity of the k-Nearest Neighbors Problem},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387649},
doi = {10.1145/3375395.3387649},
abstract = {We consider static, external memory indexes for exact and approximate versions of the k-nearest neighbor (k-NN) problem, and show new lower bounds under a standard indivisibility assumption: Polynomial space indexing schemes for high-dimensional k-NN in Hamming space cannot take advantage of block transfers: \'{\i}(k) block reads are needed to to answer a query. For the l∞ metric the lower bound holds even if we allow c-appoximate nearest neighbors to be returned, for c ∈ (1, 3). The restriction to c < 3 is necessary: For every metric there exists an indexing scheme in the indexability model of Hellerstein et al. using space O(kn), where n is the number of points, that can retrieve k 3-approximate nearest neighbors using optimal ⌈k/B⌉ I/Os, where B is the block size. For specific metrics, data structures with better approximation factors are possible. For k-NN in Hamming space and every approximation factor c>1 there exists a polynomial space data structure that returns k c-approximate nearest neighbors in ⌈k/B⌉ I/Os. To show these lower bounds we develop two new techniques: First, to handle that approximation algorithms have more freedom in deciding which result set to return we develop a relaxed version of the λ-set workload technique of Hellerstein et al. This technique allows us to show lower bounds that hold in d ≥ n dimensions. To extend the lower bounds down to d = O(k log(n/k)) dimensions, we develop a new deterministic dimension reduction technique that may be of independent interest.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {205–212},
numpages = {8},
keywords = {I/O complexity, indexability model, nearest neighbors},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387667,
author = {Agarwal, Pankaj K. and Sintos, Stavros and Steiger, Alex},
title = {Efficient Indexes for Diverse Top-k Range Queries},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387667},
doi = {10.1145/3375395.3387667},
abstract = {Let P be a set of n (non-negatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and high-valued points of P that lie inside a query range, a problem relevant to many areas such as search engines, recommendation systems, and online stores. The diversity and value of a set of points are measured as functions (say average or minimum) of their pairwise distances and weights, respectively. We study both bicriteria and constrained optimization problems. In the former, we wish to return a set of k points that maximize a weighted sum of their value and diversity measures, and in the latter, we wish to return a set of at most k points that maximize their value and satisfy a diversity constraint. We obtain three main types of results in this paper: Near-linear time (0.5-ε)-approximation algorithms for the bicriteria optimization problem in the offline setting. Near-linear size indexes for the bicriteria optimization problem that for a query rectangle return a (0.5-ε)-approximate solution in time O(k polylog(n)). The indexes can be constructed in O(n polylog(n)) time. Near-linear size indexes for answering constrained optimization range queries. For a query rectangle, a 0.5O(d)-approximate solution can be computed in O(k polylog(n)) time. If we allow some of the returned points to lie at most ε outside of the query rectangle then an (1-ε)-approximate solution can be computed in O(k polylog(n)) time. The indexes are constructed in O(n polylog(n)) and nO(1/εd) time, respectively.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {213–227},
numpages = {15},
keywords = {representative set, weighted euclidean, diversity maximization, range query, eps-net, dispersion, top-k},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3389131,
author = {Darwiche, Adnan},
title = {Three Modern Roles for Logic in AI},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3389131},
doi = {10.1145/3375395.3389131},
abstract = {We consider three modern roles for logic in artificial intelligence, which are based on the theory of tractable Boolean circuits: (1) logic as a basis for computation, (2) logic for learning from a combination of data and knowledge, and (3) logic for reasoning about the behavior of machine learning systems.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {229–243},
numpages = {15},
keywords = {explainable AI, knowledge compilation, tractable circuits},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387644,
author = {Gogacz, Tomasz and Marcinkowski, Jerzy and Pieris, Andreas},
title = {All-Instances Restricted Chase Termination},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387644},
doi = {10.1145/3375395.3387644},
abstract = {The chase procedure is a fundamental algorithmic tool in database theory with a variety of applications. A key problem concerning the chase procedure is all-instances termination: for a given set of tuple-generating dependencies (TGDs), is it the case that the chase terminates for every input database? In view of the fact that this problem is undecidable, it is natural to ask whether known well-behaved classes of TGDs ensure decidability. We consider here the main paradigms that led to robust TGD-based formalisms, that is, guardedness and stickiness. Although all-instances termination is well-understood for the oblivious chase, the more subtle case of the restricted (a.k.a. the standard) chase is rather unexplored. We show that all-instances restricted chase termination for guarded/sticky single-head TGDs is decidable in elementary time.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {245–258},
numpages = {14},
keywords = {guardedness, stickiness, restricted chase, chase termination, tuple-generating dependencies, decidability},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387653,
author = {Barcelo, Pablo and Dalmau, Victor and Feier, Cristina and Lutz, Carsten and Pieris, Andreas},
title = {The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387653},
doi = {10.1145/3375395.3387653},
abstract = {Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus derive additional facts from the given data, while in querying in the presence of constraints, they restrict the set of admissible databases. In this work, we study the limits of efficient query evaluation in the context of the above two problems, focusing on guarded and frontier-guarded TGDs and on UCQs as the actual queries. We show that a class of ontology-mediated queries (OMQs) based on guarded TGDs can be evaluated in FPT iff the OMQs in the class are equivalent to OMQs in which the actual query has bounded treewidth, up to some reasonable assumptions. For querying in the presence of constraints, we consider classes of constraint-query specifications (CQSs) that bundle a set of constraints with an actual query. We show a dichotomy result for CQSs based on guarded TGDs that parallels the one for OMQs except that, additionally, FPT coincides with PTime combined complexity. The proof is based on a novel connection between OMQ and CQS evaluation. Using a direct proof, we also show a similar dichotomy result, again up to some reasonable assumptions, for CQSs based on frontier-guarded TGDs with a bounded number of atoms in TGD heads. Our results on CQSs can be viewed as extensions of Grohe's well-known characterization of the tractable classes of CQs (without constraints). Like Grohe's characterization, all the above results assume that the arity of relation symbols is bounded by a constant. We also study the associated meta problems, i.e., whether a given OMQ or CQS is equivalent to one in which the actual query has bounded treewidth.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {259–270},
numpages = {12},
keywords = {ontology-mediated queries, query evaluation, complexity, treewidth, conjunctive queries, tuple-generating dependencies, fixed-parameter tractability, guardedness},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387647,
author = {Freire, Cibele and Gatterbauer, Wolfgang and Immerman, Neil and Meliou, Alexandra},
title = {New Results for the Complexity of Resilience for Binary Conjunctive Queries with Self-Joins},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387647},
doi = {10.1145/3375395.3387647},
abstract = {The resilience of a Boolean query on a database is the minimum number of tuples that need to be deleted from the input tables in order to make the query false. A solution to this problem immediately translates into a solution for the more widely known problem of deletion propagation with source-side effects. In this paper, we give several novel results on the hardness of the resilience problem for conjunctive queries with self-joins, and, more specifically, we present a dichotomy result for the class of single-self-join binary queries with exactly two repeated relations occurring in the query. Unlike in the self-join free case, the concept of triad is not enough to fully characterize the complexity of resilience. We identify new structural properties, namely chains, confluences and permutations, which lead to various NP-hardness results. We also give novel involved reductions to network flow to show certain cases are in P. Although restricted, our results provide important insights into the problem of self-joins that we hope can help solve the general case of all conjunctive queries with self-joins in the future.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {271–284},
numpages = {14},
keywords = {complexity, dichotomy, resilience, self-join},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387664,
author = {Reshef, Alon and Kimelfeld, Benny and Livshits, Ester},
title = {The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387664},
doi = {10.1145/3375395.3387664},
abstract = {The Shapley value is a conventional and well-studied function for determining the contribution of a player to the coalition in a cooperative game. Among its applications in a plethora of domains, it has recently been proposed to use the Shapley value for quantifying the contribution of a tuple to the result of a database query. In particular, we have a thorough understanding of the tractability frontier for the class of Conjunctive Queries (CQs) and aggregate functions over CQs. It has also been established that a tractable (randomized) multiplicative approximation exists for every union of CQs. Nevertheless, all of these results are based on the monotonicity of CQs. In this work, we investigate the implication of negation on the complexity of Shapley computation, in both the exact and approximate senses. We generalize a known dichotomy to account for negated atoms. We also show that negation fundamentally changes the complexity of approximation. We do so by drawing a connection to the problem of deciding whether a tuple is "relevant" to a query, and by analyzing its complexity.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {285–297},
numpages = {13},
keywords = {conjunctive queries, shapley value, query answering},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387651,
author = {Segoufin, Luc and Vianu, Victor},
title = {Projection Views of Register Automata},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387651},
doi = {10.1145/3375395.3387651},
abstract = {Register automata have been used as a convenient model for specifying and verifying database driven systems. An important problem in such systems is to provide views that hide or restructure certain information about the data or process, extending classical notions of database views. In this paper we carry out a formal investigation of views of register automata by considering simple views that project away some of the registers. We show that classical register automata are not able to describe such projections and introduce more powerful register automata that are able to do so. We also show useful properties of these automata such as closure under projection and decidability of verifying temporal properties of their runs.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {299–313},
numpages = {15},
keywords = {data-driven workflows, register automata, projection views},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387655,
author = {Ketsman, Bas and Koch, Christoph and Neven, Frank and Vandevoort, Brecht},
title = {Deciding Robustness for Lower SQL Isolation Levels},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387655},
doi = {10.1145/3375395.3387655},
abstract = {While serializability always guarantees application correctness, lower isolation levels can be chosen to improve transaction throughput at the risk of introducing certain anomalies. A set of transactions is robust against a given isolation level if every possible interleaving of the transactions under the specified isolation level is serializable. Robustness therefore always guarantees application correctness with the performance benefit of the lower isolation level. While the robustness problem has received considerable attention in the literature, only sufficient conditions have been obtained. The most notable exception is the seminal work by Fekete where he obtained a characterization for deciding robustness against SNAPSHOT ISOLATION. In this paper, we address the robustness problem for the lower SQL isolation levels READ UNCOMMITTED and READ COMMITTED which are defined in terms of the forbidden dirty write and dirty read patterns. The first main contribution of this paper is that we characterize robustness against both isolation levels in terms of the absence of counter example schedules of a specific form (split and multi-split schedules) and by the absence of cycles in interference graphs that satisfy various properties. A critical difference with Fekete's work, is that the properties of cycles obtained in this paper have to take the relative ordering of operations within transactions into account as READ UNCOMMITTED and READ COMMITTED do not satisfy the atomic visibility requirement. A particular consequence is that the latter renders the robustness problem against READ COMMITTED coNP-complete. The second main contribution of this paper is the coNP-hardness proof. For READ UNCOMMITTED, we obtain LOGSPACE-completeness.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {315–330},
numpages = {16},
keywords = {concurrency control, theory, transactions, robustness, optimization},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3389130,
author = {Durand, Arnaud},
title = {Fine-Grained Complexity Analysis of Queries: From Decision to Counting and Enumeration},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3389130},
doi = {10.1145/3375395.3389130},
abstract = {This paper is devoted to a complexity study of various tasks related to query answering such as deciding if a Boolean query is true or not, counting the size of the answer set or enumerating the results. It is a survey of some of the many tools from complexity measures trough algorithmic methods to conditional lower bounds that have been designed in the domain over the last years.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {331–346},
numpages = {16},
keywords = {counting, enumeration algorithm, logic, query evaluation},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387659,
author = {Grohe, Martin and Kaminski, Benjamin Lucien and Katoen, Joost-Pieter and Lindner, Peter},
title = {Generative Datalog with Continuous Distributions},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387659},
doi = {10.1145/3375395.3387659},
abstract = {Arguing for the need to combine declarative and probabilistic programming, B\'{a}r\'{a}ny et al. (TODS 2017) recently introduced a probabilistic extension of Datalog as a "purely declarative probabilistic programming language." We revisit this language and propose a more foundational approach towards defining its semantics. It is based on standard notions from probability theory known as stochastic kernels and Markov processes. This allows us to extend the semantics to continuous probability distributions, thereby settling an open problem posed by B\'{a}r\'{a}ny et al. We show that our semantics is fairly robust, allowing both parallel execution and arbitrary chase orders when evaluating a program. We cast our semantics in the framework of infinite probabilistic databases (Grohe and Lindner, ICDT 2020), and we show that the semantics remains meaningful even when the input of a probabilistic Datalog program is an arbitrary probabilistic database.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {347–360},
numpages = {14},
keywords = {datalog, probabilistic databases, generative datalog, measure theory, stochastic kernels, probabilistic programming},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387663,
author = {Schmid, Markus L.},
title = {Conjunctive Regular Path Queries with String Variables},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387663},
doi = {10.1145/3375395.3387663},
abstract = {We introduce the class CXRPQ of conjunctive xregex path queries, which are obtained from conjunctive regular path queries (CRPQs) by adding string variables (also called backreferences) as found in practical implementations of regular expressions. CXRPQs can be considered user-friendly, since they combine two concepts that are well-established in practice: pattern-based graph queries and regular expressions with backreferences. Due to the string variables, CXRPQs can express inter-path dependencies, which are not expressible by CRPQs. The evaluation complexity of CXRPQs, if not further restricted, is PSpace-hard in data complexity. We identify three natural fragments with more acceptable evaluation complexity: their data complexity is in NL, while their combined complexity varies between ExpSpace, PSpace and NP. In terms of expressive power, we compare the CXRPQ-fragments with CRPQs and unions of CRPQs, and with extended conjunctive regular path queries (ECRPQs) and unions of ECRPQs.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {361–374},
numpages = {14},
keywords = {conjunctive regular path queries, graph databases},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387646,
author = {Kara, Ahmet and Nikolic, Milos and Olteanu, Dan and Zhang, Haozhe},
title = {Trade-Offs in Static and Dynamic Evaluation of Hierarchical Queries},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387646},
doi = {10.1145/3375395.3387646},
abstract = {We investigate trade-offs in static and dynamic evaluation of hierarchical queries with arbitrary free variables. In the static setting, the trade-off is between the time to partially compute the query result and the delay needed to enumerate its tuples. In the dynamic setting, we additionally consider the time needed to update the query result under single-tuple inserts or deletes to the database.Our approach observes the degree of values in the database and uses different computation and maintenance strategies for high-degree (heavy) and low-degree (light) values. For the latter it partially computes the result, while for the former it computes enough information to allow for on-the-fly enumeration.The main result of this work defines the preprocessing time, the update time, and the enumeration delay as functions of the light/heavy threshold. By conveniently choosing this threshold, our approach recovers a number of prior results when restricted to hierarchical queries.For a restricted class of hierarchical queries, our approach can achieve worst-case optimal update time and enumeration delay conditioned on the Online Matrix-Vector Multiplication Conjecture.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {375–392},
numpages = {18},
keywords = {incremental view maintenance, sublinear update time, sublinear enumeration delay, adaptive query evaluation, hierarchical queries},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387662,
author = {Carmeli, Nofar and Zeevi, Shai and Berkholz, Christoph and Kimelfeld, Benny and Schweikardt, Nicole},
title = {Answering (Unions of) Conjunctive Queries Using Random Access and Random-Order Enumeration},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387662},
doi = {10.1145/3375395.3387662},
abstract = {As data analytics becomes more crucial to digital systems, so grows the importance of characterizing the database queries that admit a more efficient evaluation. We consider the tractability yardstick of answer enumeration with a polylogarithmic delay after a linear-time preprocessing phase. Such an evaluation is obtained by constructing, in the preprocessing phase, a data structure that supports polylogarithmic-delay enumeration. In this paper, we seek a structure that supports the more demanding task of a "random permutation": polylogarithmic-delay enumeration in truly random order. Enumeration of this kind is required if downstream applications assume that the intermediate results are representative of the whole result set in a statistically valuable manner. An even more demanding task is that of a "random access": polylogarithmic-time retrieval of an answer whose position is given. We establish that the free-connex acyclic CQs are tractable in all three senses: enumeration, random-order enumeration, and random access; and in the absence of self-joins, it follows from past results that every other CQ is intractable by each of the three (under some fine-grained complexity assumptions). However, the three yardsticks are separated in the case of a union of CQs (UCQ): while a union of free-connex acyclic CQs has a tractable enumeration, it may (provably) admit no random access. For such UCQs we devise a random-order enumeration whose delay is logarithmic in expectation. We also identify a subclass of UCQs for which we can provide random access with polylogarithmic access time. Finally, we present an implementation and an empirical study that show a considerable practical superiority of our random-order enumeration approach over state-of-the-art alternatives.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {393–409},
numpages = {17},
keywords = {complexity, enumeration, unions of conjunctive queries},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387657,
author = {Hu, Xiao and Yi, Ke},
title = {Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387657},
doi = {10.1145/3375395.3387657},
abstract = {In this paper, we design massively parallel algorithms for sparse matrix multiplication, as well as more general join-aggregate queries, where the join hypergraph is a tree with arbitrary output attributes. For each case, we obtain asymptotic improvement over existing algorithms. In particular, our matrix multiplication algorithm is shown to be optimal in the semiring model.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {411–425},
numpages = {15},
keywords = {sparse matrix multiplication, parallel algorithms, join-aggregate query},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387660,
author = {Toru\'{n}czyk, Szymon},
title = {Aggregate Queries on Sparse Databases},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387660},
doi = {10.1145/3375395.3387660},
abstract = {We propose an algebraic framework for studying efficient algorithms for query evaluation, aggregation, enumeration, and maintenance under updates, on sparse databases. Our framework allows to treat those problems in a unified way, by considering various semirings, depending on the considered problem. As a concrete application, we propose a powerful query language extending first-order logic by aggregation in multiple semirings. We obtain an optimal algorithm for computing the answers of such queries on sparse databases. More precisely, given a database from a fixed class with bounded expansion, the algorithm computes in linear timea data structure which allows to enumerate the set of answers to the query, with constant delay between two outputs.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {427–443},
numpages = {17},
keywords = {sparse graphs, enumeration, bounded expansion, provenance, updates, semiring circuits, query evaluation},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387652,
author = {McGregor, Andrew and Vorotnikova, Sofya},
title = {Triangle and Four Cycle Counting in the Data Stream Model},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387652},
doi = {10.1145/3375395.3387652},
abstract = {The problem of estimating the number of cycles in a graph is one of the most widely studied graph problems in the data stream model. Three relevant variants of the data stream model include: the arbitrary order model in which the stream consists of the edges of the graph in arbitrary order, the random order model in which the edges are randomly permuted, and the adjacency list order model in which all edges incident to the same vertex appear consecutively. In this paper, we focus on the problem of triangle and four-cycle counting in these models. We improve over the state-of-the-art results as follows, where n is the number of vertices, m is the number of edges and T is the number of triangles/four-cycles in the graph (i.e., the quantity being estimated): Random Order Model: We present a single-pass algorithm that (1+ε)-approximates the number of triangles using ~O(ε-2 m/√T) space and prove that this is optimal in the range T ≤ √m. The best previous result, a (3+ε)-approximation using ~O(ε-4.5 m/√T) space, was presented by Cormode and Jowhari~(Theor. Comput. Sci. 2017). Adjacency List Model: We present an algorithm that returns a (1+ε)-approximation of the number of 4-cycles using two passes and ~O(ε-4 m/√T) space. The best previous result, a constant approximation using ~O(m/T3/8) space, was presented by Kallaugher et al. (PODS~2019). We also show that (1+ε)-approximation in a single pass is possible in a) polylog(n) space if T=Ω(n2) and b) ~O(n) space if T=Ω(n). Arbitrary Order Model: We present a three-pass algorithm that (1+ε)-approximates the number of 4-cycles using ~O(ε-2 m/T1/4) space and a one-pass algorithm that uses ~O(ε-2 n) space when T=Ω(n2). The best existing result, a (1+ε)-approximation using ~O(ε-2 m2/T) space, was presented by Bera and Chakrabarti (STACS~2017). We also show a multi-pass lower bound and another algorithm for distinguishing graphs with no four cycles and graphs with many 4-cycles.},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {445–456},
numpages = {12},
keywords = {triangles, cycles, data streams},
location = {Portland, OR, USA},
series = {PODS'20}
}

@inproceedings{10.1145/3375395.3387665,
author = {Bera, Suman K. and Seshadhri, C.},
title = {How the Degeneracy Helps for Triangle Counting in Graph Streams},
year = {2020},
isbn = {9781450371087},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3375395.3387665},
doi = {10.1145/3375395.3387665},
abstract = {We revisit the well-studied problem of triangle count estimation in graph streams. Given a graph represented as a stream of m edges, our aim is to compute a (1+-ε)-approximation to the triangle count T, using a small space algorithm. For arbitrary order and a constant number of passes, the space complexity is known to be essentially Θ(min(m3/2 /T, m/√T)) (McGregor et al., PODS 2016, Bera et al., STACS 2017). We give a (constant pass, arbitrary order) streaming algorithm that can circumvent this lower bound for low degeneracy graphs. The degeneracy, K, is a nuanced measure of density, and the class of constant degeneracy graphs is immensely rich (containing planar graphs, minor-closed families, and preferential attachment graphs). We design a streaming algorithm with space complexity ~O(mK/T). For constant degeneracy graphs, this bound is ~O(m/T), which is significantly smaller than both m3/2 /T and m/√T. We complement our algorithmic result with a nearly matching lower bound of Ω(mK/T).},
booktitle = {Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems},
pages = {457–467},
numpages = {11},
keywords = {triangle counting, streaming model, degeneracy},
location = {Portland, OR, USA},
series = {PODS'20}
}

license: Unlicense

repository: goyalkaraniit/acm-cr

repo_name: goyalkaraniit/acm-cr

branch_name: refs/heads/main


text:
file(REMOVE_RECURSE
  "CMakeFiles/kbmod.dir/__/src/kbmod_generated_kernels.cu.o"
  "CMakeFiles/kbmod.dir/classBindings.cpp.o"
  "kbmod.pdb"
  "kbmod.cpython-35m-x86_64-linux-gnu.so"
)

# Per-language clean rules from dependency scanning.
foreach(lang CXX)
  include(CMakeFiles/kbmod.dir/cmake_clean_${lang}.cmake OPTIONAL)
endforeach()

repository: PWhiddy/kbmod

license_type: permissive

repo_name: PWhiddy/kbmod

branch_name: refs/heads/master

extension: cmake


text:
@online{24_how_nodate,
	title = {How to Tell a Story with Data},
	url = {http://blogs.hbr.org/2013/04/how-to-tell-a-story-with-data/},
	abstract = {Five rules for doing it right.},
	titleaddon = {Harvard Business Review},
	author = {24, Jim Stikeleather 11:00 AM April and {2013}},
	urldate = {2014-04-21}
}

repository: pmean/build-website

repo_name: pmean/build-website

extension: bib


text:
@ONLINE {rps,
author = "Laurence Moroney",
title = "Rock, Paper, Scissors Dataset",
month = "feb",
year = "2019",
url = "http://laurencemoroney.com/rock-paper-scissors-dataset"
}

repository: tensorflow/datasets

repo_name: tensorflow/datasets

gha_language: Python


text:
require ti-sysbios.inc

PV = "6_21_01_16"

SRC_URI[sysbiosbin.md5sum] = "411cd0fac224126ed2a81e67fc79c81a"
SRC_URI[sysbiosbin.sha256sum] = "63d2704ff294fe0834411d010d19c0a0bfd0249520f5ee5ddc2c115df2be8ddd"

license: MIT

repository: overo/overo-oe-natty

repo_name: overo/overo-oe-natty

branch_name: HEAD

extension: bb


text:
// Copyright 2021 VMware, Inc. All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0

package cmd

import (
	"github.com/spf13/cobra"
)

var updateCredsCommand = &cobra.Command{
	Use:   "update-credentials",
	Short: "Update a Tanzu Kubernetes cluster credentials",
	Long:  "Update a Tanzu Kubernetes cluster credentials",
}

func init() {
	RootCmd.AddCommand(updateCredsCommand)
}

repository: spagno/tanzu-framework

repo_name: spagno/tanzu-framework

extension: go


text:
package options

import (
	"time"

	utilhaproxy "github.com/adohe/kube2haproxy/util/haproxy"
	utilkeepalived "github.com/adohe/kube2haproxy/util/keepalived"

	"github.com/spf13/pflag"
)

// ProxyServerConfig configures and runs the proxy server.
type ProxyServerConfig struct {
	BindAddress      string
	Address          string
	Port             int
	KubeAPIQPS       float32
	KubeAPIBurst     int
	Master           string
	SyncPeriod       time.Duration
	Kubeconfig       string
	EnableProfiling  bool
	Device           string
	KeepalivedConfig utilkeepalived.KeepalivedConfig
	HaproxyConfig    utilhaproxy.HaproxyConfig
}

func NewProxyServerConfig() *ProxyServerConfig {
	return &ProxyServerConfig{
		KubeAPIQPS:      5.0,
		KubeAPIBurst:    10,
		SyncPeriod:      30 * time.Minute,
		EnableProfiling: false,
		KeepalivedConfig: utilkeepalived.KeepalivedConfig{
			ConfigPath:     "/etc/keepalived/keepalived.conf",
			ReloadInterval: time.Duration(2 * time.Second),
		},
		HaproxyConfig: utilhaproxy.HaproxyConfig{
			ConfigPath:     "/etc/haproxy/haproxy.cfg",
			ReloadInterval: time.Duration(5 * time.Second),
		},
	}
}

// AddFlags adds flags for a specific ProxyServer to the specified FlagSet.
func (s *ProxyServerConfig) AddFlags(fs *pflag.FlagSet) {
	fs.StringVar(&s.Address, "address", s.Address, "The IP address to serve on (set to 0.0.0.0 for all interfaces)")
	fs.IntVar(&s.Port, "port", s.Port, "The port that the proxy's http service runs on")
	fs.Float32Var(&s.KubeAPIQPS, "kube-api-qps", s.KubeAPIQPS, "QPS to use while talking with kubernetes apiserver")
	fs.IntVar(&s.KubeAPIBurst, "kube-api-burst", s.KubeAPIBurst, "Burst to use while talking with kubernets apiserver")
	fs.StringVar(&s.Master, "master", s.Master, "The address of the kubernetes apiserver")
	fs.DurationVar(&s.SyncPeriod, "sync-period", s.SyncPeriod, "How often configuration from the apiserver is refreshed. Must be greater than 0")
	fs.StringVar(&s.Kubeconfig, "kubeconfig", s.Kubeconfig, "Path to kubeconfig file with authorization information (the master location is set by the master flag).")
	fs.BoolVar(&s.EnableProfiling, "profiling", s.EnableProfiling, "Set true to enable pprof")
	fs.StringVar(&s.Device, "device", s.Device, "Network device to bind service IP")
	fs.StringVar(&s.KeepalivedConfig.ConfigPath, "keepalived-config-file", s.KeepalivedConfig.ConfigPath, "Path of config file for keepalived")
	fs.StringVar(&s.KeepalivedConfig.TemplatePath, "keepalived-template-file", s.KeepalivedConfig.TemplatePath, "Path of keepalived config template")
	fs.DurationVar(&s.KeepalivedConfig.ReloadInterval, "keepalived-reload-interval", s.KeepalivedConfig.ReloadInterval, "Controls how often keepalived reload is invoked")
	fs.StringVar(&s.KeepalivedConfig.ReloadScriptPath, "keepalived-reload-script", s.KeepalivedConfig.ReloadScriptPath, "Path of keepalived reload script")
	fs.StringVar(&s.HaproxyConfig.ConfigPath, "haproxy-config-file", s.HaproxyConfig.ConfigPath, "Path of config file for haproxy")
	fs.StringVar(&s.HaproxyConfig.TemplatePath, "haproxy-template-file", s.HaproxyConfig.TemplatePath, "Path of haproxy template")
	fs.DurationVar(&s.HaproxyConfig.ReloadInterval, "haproxy-reload-interval", s.HaproxyConfig.ReloadInterval, "Controls how often haproxy reload is invoked")
	fs.StringVar(&s.HaproxyConfig.ReloadScriptPath, "haproxy-reload-script", s.HaproxyConfig.ReloadScriptPath, "Path of haproxy reload script")
	fs.StringVar(&s.HaproxyConfig.ConfiguePath, "haproxy-configuePath", s.HaproxyConfig.ConfiguePath, "Path of haproxy service files")
	fs.StringVar(&s.HaproxyConfig.PidPath, "haproxy-pidpath", s.HaproxyConfig.PidPath, "Path of haproxy pid files")
	fs.StringVar(&s.HaproxyConfig.ExecFile, "haproxy-execPath", s.HaproxyConfig.ExecFile, "Path of haproxy")
}


text:
package models

import (
	"encoding/json"
	"time"
)

type Log struct {
	CharacterID string `json:"characterId" redis:"characterId"`
	Message     string `json:"message" redis:"message"`
	Timestamp   int64  `json:"timestamp" redis:"timestamp"`
}

func NewLog(characterID, message string) *Log {
	return &Log{
		CharacterID: characterID,
		Message:     message,
		Timestamp:   time.Now().Unix(),
	}
}

func (c *Log) MarshalBinary() ([]byte, error) {
	return json.Marshal(c)
}

func (c *Log) UnmarshalBinary(data []byte) error {
	return json.Unmarshal(data, c)
}


text:
@article{CitekeyArticle,
 number        = {6},
 pages         = {1143--1148},
 author        = {Cohen, P.  J.},
 year          = {1963},
 volume        = {50},
 journal       = {Proceedings of the National Academy of Sciences},
 title         = {The independence of the continuum hypothesis}
}

@book{CitekeyBook,
 publisher     = {Penguin Random House},
 address       = {New York, NY},
 author        = {Susskind, Leonard and Hrabovsky, George},
 year          = {2014},
 title         = {Classical mechanics: the theoretical minimum}
}

gha_license_id: MIT

gha_language: Julia


text:
DESCRIPTION = "Easy to use task manager"
LICENSE = "GPLv2"
LIC_FILES_CHKSUM = "file://COPYING;md5=94d55d512a9ba36caa9b7df079bae19f"

inherit xfce-app

DEPENDS = "gtk+ cairo libwnck xfce4-dev-tools-native exo-native"

SRC_URI = " \
    git://git.xfce.org/apps/xfce4-taskmanager;protocol=git \
    file://0001-do-not-build-documantation-Makefile-has-no-install-t.patch \
"

SRCREV = "e5d958738b6d2828a4c8353df67d3c1656c46af5"
S = "${WORKDIR}/git"
PV = "1.0.0+git${SRCPV}"

EXTRA_OECONF += "--enable-maintainer-mode"

do_configure_prepend() {
       NOCONFIGURE=yes ./autogen.sh
}

repository: ExorEmbedded/exor-workspace

repo_name: ExorEmbedded/exor-workspace


text:
@Article{Utthawang_2012,
  doi = {10.3923/sscience.2012.308.315},
  url = {https://doi.org/10.3923/sscience.2012.308.315},
  year = {2012},
  month = {feb},
  publisher = {Science Alert},
  volume = {7},
  number = {2},
  pages = {308--315},
  author = {Phannikar Utthawang and Prayoon Wongchantr and Prasat Neungchale},
  title = {The Multiple Intelligences Integrated Learning of Environmental Education to Promote Knowledge, Attitude and Awareness about Environmental Conservation of Chiang Mai Rajabhat Universnity Studets},
  journal = {The Social Sciences},
}

@Article{Azman_2010,
  doi = {10.1016/j.sbspro.2010.10.068},
  url = {https://doi.org/10.1016/j.sbspro.2010.10.068},
  year = {2010},
  publisher = {Elsevier {BV}},
  volume = {7},
  pages = {504--511},
  author = {Norzaini Azman and Sharina Abdul Halim and Ong Puay Liu and Salsela Saidin and Ibrahim Komoo},
  title = {Public Education in Heritage Conservation for Geopark Community},
  journal = {Procedia - Social and Behavioral Sciences},
}

@Article{Dolins_2009,
  doi = {10.1002/ajp.20779},
  url = {https://doi.org/10.1002/ajp.20779},
  year = {2009},
  month = {dec},
  publisher = {Wiley-Blackwell},
  volume = {72},
  number = {5},
  pages = {391--406},
  author = {Francine L. Dolins and Alison Jolly and Hantanirina Rasamimanana and Jonah Ratsimbazafy and Anna T.C. Feistner and Florent Ravoavy},
  title = {Conservation education in Madagascar: three case studies in the biologically diverse island-continent},
  journal = {American Journal of Primatology},
}

@Article{Kuhar_2009,
  doi = {10.1002/ajp.20726},
  url = {https://doi.org/10.1002/ajp.20726},
  year = {2009},
  month = {jul},
  publisher = {Wiley-Blackwell},
  volume = {72},
  number = {5},
  pages = {407--413},
  author = {C.W. Kuhar and T.L. Bettinger and K. Lehnhardt and Osuo Tracy and D. Cox},
  title = {Evaluating for long-term impact of an environmental education program at the Kalinzu Forest Reserve, Uganda},
  journal = {American Journal of Primatology},
}

@Article{Macharia_2010,
  doi = {10.1080/14888386.2010.9712652},
  url = {https://doi.org/10.1080/14888386.2010.9712652},
  year = {2010},
  month = {sep},
  publisher = {Informa {UK} Limited},
  volume = {11},
  number = {1-2},
  pages = {85--90},
  author = {Jane M. Macharia and Thuita Thenya and George G. Ndiritu},
  title = {Management of highland wetlands in central Kenya: the importance of community education, awareness and eco-tourism in biodiversity conservation},
  journal = {Biodiversity},
}

@Article{SCHOLTE_2005,
  doi = {10.1017/s0376892905002523},
  url = {https://doi.org/10.1017/s0376892905002523},
  year = {2005},
  month = {dec},
  publisher = {Cambridge University Press ({CUP})},
  volume = {32},
  number = {04},
  pages = {349},
  author = {PAUL SCHOLTE and WOUTER T. DE GROOT and ZACHARIE MAYNA and 4 TALLA},
  title = {Protected area managers{\textquotesingle} perceptions of community conservation training in West and Central Africa},
  journal = {Envir. Conserv.},
}

repository: marty-downs/evidence-based-heatmap

repo_name: marty-downs/evidence-based-heatmap


text:
@article{vangessel2018phonon,
      title={A Phonon Boltzmann Study of Microscale Thermal Transport in $\alpha$-RDX Cook-Off},
      author={Francis G. VanGessel and Gaurav Kumar and Daniel C. Elton and Peter W. Chung},
      year={2018},
      journal = {Proceedings of the 22nd International Seminar on New Trends in Research of Energetic Materials},
      arxiv = {https://arxiv.org/abs/1808.08295}
}

gha_language: HTML


text:
@inproceedings{cohen2021TSC,
 author = {Cohen, A and Mulder, B and Prohl, A and Soussand, L and Davis, P and Kroeck, M and McManus, P and Gholipour, A and Scherrer, B and Sahin, M and Krueger, D and Bebin, E and others},
 booktitle = {ANNALS OF NEUROLOGY},
 organization = {WILEY 111 RIVER ST, HOBOKEN 07030-5774, NJ USA},
 pages = {726-739},
 title = {Tubers Associated with Infantile Spasms Impact a Common Brain Network in Tuberous Sclerosis Complex},
 volume = {89},
 year = {2021}
}

repository: bchcohenlab/academic-kickstart

repo_name: bchcohenlab/academic-kickstart


text:
package main

import (
	"github.com/gorilla/mux"
	"net/http"
)

const IDPath = "/lpatmore"

func main() {
	r := mux.NewRouter()
	r.HandleFunc("/", HomeHandler)

	s := r.PathPrefix(IDPath).Subrouter()
	s.HandleFunc("/all", GetAllDBRowsHandler).Methods("GET")
	s.HandleFunc("/status", GetDBStatusHandler).Methods("GET")

	_ = http.ListenAndServe(":8080", r)
}

repository: LandonPatmore/jobListingsServer

repo_name: LandonPatmore/jobListingsServer


text:
@misc{appralgo,
  Author = {Gharan, Shayan Oveis},
  Institution = {University of Washington Computer Science & Engineering},
  Howpublished = {University Lecture},
  Url = {https://homes.cs.washington.edu/~shayan/courses/approx/},
  Year = {2015},
  Title = {Recent Developments in Approximation Algorithms}
}

@book{godsil2001algebraic,
  title={Algebraic Graph Theory},
  author={Godsil, C. and Royle, G.F.},
  isbn={9780387952208},
  lccn={lc00053776},
  series={Graduate Texts in Mathematics},
  url={https://books.google.co.in/books?id=gk60QgAACAAJ},
  year={2001},
  publisher={Springer New York}
}

@article{GUENOCHE1983214,
title = "Random spanning tree",
journal = "Journal of Algorithms",
volume = "4",
number = "3",
pages = "214 - 220",
year = "1983",
issn = "0196-6774",
doi = "https://doi.org/10.1016/0196-6774(83)90022-6",
url = "http://www.sciencedirect.com/science/article/pii/0196677483900226",
author = "A Guénoche",
abstract = "Dans cet article, nous proposons un algorithme de complexité polynomiale pour construire un arbre au hasard qui soit un graphe partiel d'un graphe donné. Il consiste essentielleement à construire une arborescence de rang donné sur ce graphe, l'ensemble des arborescences étant ordonné par rapport aux valeurs croissantes de la racine et à racine égale suivant l'ordre lexicographique du codage utilisé pour les arborescences."
}

@article{burton1993,
author = "Burton, Robert and Pemantle, Robin",
doi = "10.1214/aop/1176989121",
fjournal = "Annals of Probability",
journal = "Ann. Probab.",
month = "07",
number = "3",
pages = "1329--1371",
publisher = "The Institute of Mathematical Statistics",
title = "Local Characteristics, Entropy and Limit Theorems for Spanning Trees and Domino Tilings Via Transfer-Impedances",
url = "https://doi.org/10.1214/aop/1176989121",
volume = "21",
year = "1993"
}

repository: kishlaya/assignments

repo_name: kishlaya/assignments


text:
@article{Tefs-2021-Simulating,
    title = "Simulating river regulation and reservoir performance in a continental-scale hydrologic model",
    author = "Tefs, A.A.G.  and
      Stadnyk, T.A.  and
      Koenig, K.A.  and
      D{\'e}ry, S.J.  and
      MacDonald, M.K.  and
      Slota, P.  and
      Crawford, J.  and
      Hamilton, M.",
    journal = "Environmental Modelling {\&} Software, Volume 141",
    volume = "141",
    year = "2021",
    publisher = "Elsevier BV",
    url = "https://aclanthology.org/G21-21001",
    doi = "10.1016/j.envsoft.2021.105025",
    pages = "105025",
}

repository: gwf-uwaterloo/gwf-publications

repo_name: gwf-uwaterloo/gwf-publications


text:
import React from 'react'
import PropTypes from 'prop-types'
import { withRouter } from 'react-router-dom'
import { Grid, Label, Header, Input, Button, Dimmer, Loader, Image, Message, Segment, Icon } from 'semantic-ui-react'
import UploadXL from '/imports/ui/ordering/uploadXL'
import PartCard from '/imports/ui/ordering/ordering-part-card'
import PartList from '/imports/ui/ordering/ordering-part-list'
import CartIcon from '/imports/ui/ordering/cart-icon'

const Ordering = props => {
  const [addParts, setAdd] = React.useState(true)
  const [searchFor, setSearch] = React.useState('')
  const [virgin, setVirgin] = React.useState(true)

  toggleAddPart = () => {
    setAdd(!addParts)
  }

  onSearchInput = e => {
    setSearch(e.target.value)
  }

  search = e => {
    // e.preventDefault()
    props.onSearchInput(searchFor)
  }

  onKeyPress = target => {
    if (target.key === 'Enter') {
      props.onSearchInput(searchFor)
      setVirgin(false)
    }
  }

  if (props.loading) {
    return (

        <Dimmer active inverted>
          <Loader size="huge">Loading... </Loader>
        </Dimmer>

        <Image src="/images/wireframe/short-paragraph.png" />

    )
  }

  const { activeOrder, uploadXL } = props
  let noOfParts = 0
  const { parts = [] } = props
  const cartClick = () => {
    props.history.push('/parts/ordering/cart')
  }

  return (
    <Grid container columns="equal">
      {!props.loading &&
        activeOrder &&
        activeOrder.orderedParts.forEach(part => {
          noOfParts += part.qty
          return noOfParts
        })}

      <Grid.Row columns={1}>
        <Grid.Column width={16}>

            {' '}

Parts Search
{' '}

        </Grid.Column>
      </Grid.Row>
      <Grid.Row columns={1} centered>
        <CartIcon noOfParts={noOfParts} onClick={cartClick} />

        <Input
          placeholder="Part number or name"
          className="member-search"
          onChange={onSearchInput}
          defaultValue={searchFor}
          onKeyPress={onKeyPress}
          size="huge"
          fluid
        >
          <input />
          {parts.length > 0 && !virgin && (

              {parts.length}

          )}
          <Button type="submit" icon labelPosition="right" color="green" size="huge" onClick={search}>
            <Icon name="search" />
            Search
          </Button>
        </Input>
      </Grid.Row>

      <Grid.Row columns={1} centered>
        {!searchFor && (
          <Message icon="info" header="Please enter part number or name" content="and press ENTER to search" />
        )}

        {parts < 1 ? (
          <>
            <Message icon="blind" header="Nothing found" content="Please try again" />
            <Button
              onClick={toggleAddPart}
              style={{
                height: '100px',
                marginTop: '20px',
                marginBottom: '20px'
              }}
              color="grey"
            >

Add updated pricelist

            </Button>

            {addParts ? '' : <UploadXL uploadXL={props.uploadXL} toggleAddPart={toggleAddPart} />}
          </>
        ) : (
            ''
          )}
      </Grid.Row>

      {searchFor && !virgin && (
        <Grid.Row>
          <Grid.Column>
            <PartList
              title={'Part Title:'}
              parts={parts}
              activeOrder={props.activeOrder}
              addToCart={props.addToCart}
              Component={PartCard}
              componentClassName="part-card-main"
              loading={props.loading}
            />
          </Grid.Column>
        </Grid.Row>
      )}
    </Grid>
  )
}

export default withRouter(Ordering)

Ordering.propTypes = {
  activeOrder: PropTypes.object,
  addToCart: PropTypes.func.isRequired,
  parts: PropTypes.array.isRequired,
  loading: PropTypes.bool.isRequired,
  partSearchQuery: PropTypes.string,
  onSearchInput: PropTypes.func,
  uploadXL: PropTypes.func.isRequired
}

extension: js


text:
package altair

import (
	"bytes"
	"context"
	"encoding/binary"
	"encoding/json"

	"github.com/protolambda/zrnt/eth2/beacon/common"
	"github.com/protolambda/ztyp/codec"
	"github.com/protolambda/ztyp/tree"
	. "github.com/protolambda/ztyp/view"
	"gopkg.in/yaml.v3"
)

const ParticipationFlagsType = Uint8Type

type ParticipationFlags Uint8View

func AsParticipationFlags(v View, err error) (ParticipationFlags, error) {
	i, err := AsUint8(v, err)
	return ParticipationFlags(i), err
}

func (a *ParticipationFlags) Deserialize(dr *codec.DecodingReader) error {
	return (*Uint8View)(a).Deserialize(dr)
}

func (i ParticipationFlags) Serialize(w *codec.EncodingWriter) error {
	return w.WriteByte(uint8(i))
}

func (ParticipationFlags) ByteLength() uint64 {
	return 8
}

func (ParticipationFlags) FixedLength() uint64 {
	return 8
}

func (t ParticipationFlags) HashTreeRoot(hFn tree.HashFn) common.Root {
	return Uint8View(t).HashTreeRoot(hFn)
}

func (e ParticipationFlags) MarshalJSON() ([]byte, error) {
	return Uint8View(e).MarshalJSON()
}

func (e *ParticipationFlags) UnmarshalJSON(b []byte) error {
	return ((*Uint8View)(e)).UnmarshalJSON(b)
}

func (e ParticipationFlags) String() string {
	return Uint8View(e).String()
}

// Participation flag indices
const (
	TIMELY_SOURCE_FLAG_INDEX uint8 = 0
	TIMELY_TARGET_FLAG_INDEX uint8 = 1
	TIMELY_HEAD_FLAG_INDEX   uint8 = 2
)

const (
	TIMELY_SOURCE_FLAG ParticipationFlags = 1 << TIMELY_SOURCE_FLAG_INDEX
	TIMELY_TARGET_FLAG ParticipationFlags = 1 << TIMELY_TARGET_FLAG_INDEX
	TIMELY_HEAD_FLAG   ParticipationFlags = 1 << TIMELY_HEAD_FLAG_INDEX
)

// Participation flag fractions
const (
	TIMELY_SOURCE_WEIGHT common.Gwei = 14
	TIMELY_TARGET_WEIGHT common.Gwei = 26
	TIMELY_HEAD_WEIGHT   common.Gwei = 14
	SYNC_REWARD_WEIGHT   common.Gwei = 2
	PROPOSER_WEIGHT      common.Gwei = 8
	WEIGHT_DENOMINATOR   common.Gwei = 64
)

type ParticipationRegistry []ParticipationFlags

func (r ParticipationRegistry) String() string {
	out, _ := json.Marshal([]ParticipationFlags(r))
	return string(out)
}

func (r *ParticipationRegistry) UnmarshalJSON(data []byte) error {
	return json.Unmarshal(data, (*[]ParticipationFlags)(r))
}

func (r ParticipationRegistry) MarshalJSON() ([]byte, error) {
	return json.Marshal([]ParticipationFlags(r))
}

func (r *ParticipationRegistry) UnmarshalYAML(value *yaml.Node) error {
	return value.Decode((*[]ParticipationFlags)(r))
}

func (r ParticipationRegistry) MarshalYAML() (interface{}, error) {
	return ([]ParticipationFlags)(r), nil
}

func (r *ParticipationRegistry) Deserialize(spec *common.Spec, dr *codec.DecodingReader) error {
	return dr.List(func() codec.Deserializable {
		i := len(*r)
		*r = append(*r, ParticipationFlags(0))
		return &(*r)[i]
	}, ParticipationFlagsType.TypeByteLength(), uint64(spec.VALIDATOR_REGISTRY_LIMIT))
}

func (r ParticipationRegistry) Serialize(spec *common.Spec, w *codec.EncodingWriter) error {
	return w.List(func(i uint64) codec.Serializable {
		return &r[i]
	}, ParticipationFlagsType.TypeByteLength(), uint64(len(r)))
}

func (r ParticipationRegistry) ByteLength(spec *common.Spec) (out uint64) {
	return uint64(len(r)) * ParticipationFlagsType.TypeByteLength()
}

func (r *ParticipationRegistry) FixedLength(spec *common.Spec) uint64 {
	return 0 // it's a list, no fixed length
}

func (r ParticipationRegistry) HashTreeRoot(spec *common.Spec, hFn tree.HashFn) common.Root {
	return hFn.Uint8ListHTR(func(i uint64) uint8 {
		return uint8(r[i])
	}, uint64(len(r)), uint64(spec.VALIDATOR_REGISTRY_LIMIT))
}

func (r ParticipationRegistry) View(spec *common.Spec) (*ParticipationRegistryView, error) {
	typ := ParticipationRegistryType(spec)
	var buf bytes.Buffer
	if err := r.Serialize(spec, codec.NewEncodingWriter(&buf)); err != nil {
		return nil, err
	}
	data := buf.Bytes()
	dec := codec.NewDecodingReader(bytes.NewReader(data), uint64(len(data)))
	return AsParticipationRegistry(typ.Deserialize(dec))
}

func ParticipationRegistryType(spec *common.Spec) *BasicListTypeDef {
	return BasicListType(ParticipationFlagsType, uint64(spec.VALIDATOR_REGISTRY_LIMIT))
}

type ParticipationRegistryView struct {
	*BasicListView
}

func AsParticipationRegistry(v View, err error) (*ParticipationRegistryView, error) {
	c, err := AsBasicList(v, err)
	return &ParticipationRegistryView{c}, err
}

func (v *ParticipationRegistryView) GetFlags(index common.ValidatorIndex) (ParticipationFlags, error) {
	return AsParticipationFlags(v.Get(uint64(index)))
}

func (v *ParticipationRegistryView) SetFlags(index common.ValidatorIndex, score ParticipationFlags) error {
	return v.Set(uint64(index), Uint8View(score))
}

func (v *ParticipationRegistryView) Raw() (ParticipationRegistry, error) {
	length, err := v.Length()
	if err != nil {
		return nil, err
	}
	out := make(ParticipationRegistry, 0, length)
	iter := v.ReadonlyIter()
	for {
		el, ok, err := iter.Next()
		if err != nil {
			return nil, err
		}
		if !ok {
			break
		}
		out = append(out, ParticipationFlags(el.(Uint8View)))
	}
	return out, nil
}

func (v *ParticipationRegistryView) FillZeroes(length uint64) error {
	// 32 flags (uint8) per node (bytes32)
	nodesLen := (length + 31) / 32
	depth := tree.CoverDepth(v.BottomNodeLimit())
	zero := &tree.Root{}
	contents, err := tree.SubtreeFillToLength(zero, depth, nodesLen)
	if err != nil {
		return err
	}
	lengthNode := &tree.Root{}
	binary.LittleEndian.PutUint64(lengthNode[:8], length)
	return v.SetBacking(tree.NewPairNode(contents, lengthNode))
}

func ProcessParticipationFlagUpdates(ctx context.Context, spec *common.Spec, state AltairLikeBeaconState) error {
	if err := ctx.Err(); err != nil {
		return err
	}
	currentEp, err := state.CurrentEpochParticipation()
	if err != nil {
		return err
	}
	previousEp, err := state.PreviousEpochParticipation()
	if err != nil {
		return err
	}
	if err := previousEp.SetBacking(currentEp.Backing()); err != nil {
		return err
	}
	length, err := currentEp.Length()
	if err != nil {
		return err
	}
	return currentEp.FillZeroes(length)
}

repository: protolambda/zrnt

repo_name: protolambda/zrnt

gha_language: Go


text:
// Dependencies
import { ApolloClient, InMemoryCache } from '@apollo/client';

// Constants
import {
  POKEAPI_URI
} from '../../constants';

// Apollo Client
export const client = new ApolloClient({
  uri: !POKEAPI_URI ? '' : POKEAPI_URI,
  cache: new InMemoryCache(),
  credentials: 'same-origin',
});

repository: jesuskata/expo-pokedex-app

repo_name: jesuskata/expo-pokedex-app


text:
require xorg-driver-input.inc
PE = "1"
SRC_URI[archive.md5sum] = "b37a432fd87bb9f46d011622d6fce6b3"
SRC_URI[archive.sha256sum] = "f10f2cadd4120b40b3658000c87f910e3005f4d787441c7dd83b48ebbf2a11f2"


text:
@article{SimilaritySearch-2021,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S. and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={763--777},
  volume={24},
  year={2021},
  issn={1433-755X},
  doi={10.1007/s10044-020-00946-w}
  publisher={Springer}
}


text:
@online{destatis2021seeschifffahrt,
    author = {{Statistisches Bundesamt (DESTATIS)}},
    title = {{Verkehr : Seeschifffahrt : August 2021}},
    howpublished = {\url{https://www.destatis.de/DE/Themen/Branchen-Unternehmen/Transport-Verkehr/Gueterverkehr/Publikationen/Downloads-Schifffahrt/seeschifffahrt-monat-2080500211084.pdf?__blob=publicationFile}},
    note = {Accessed: 2022-01-22},
    year = 2021
}

@online{isl2015umschlagpotenzial,
    author = {{Institut für Seeverkehrswirtschaft und Logistik}},
    title = {{Prognose des Umschlagpotenzials und des Modal Splits des Hamburger Hafens für die Jahre 2020, 2025 und 2030}},
    howpublished = {\url{https://www.hamburg-port-authority.de/fileadmin/user_upload/Endbericht_Potenzialprognose_Mai2015_5.pdf}},
    note = {Accessed: 2022-02-17},
    year = 2015
}

@online{hafenhamburg2020modalsplit,
    author = {{Hafen Hamburg}},
    title = {{Modal-Split im Hinterlandverkehr 2020}},
    howpublished = {\url{https://www.hafen-hamburg.de/de/statistiken/modal-split/}},
    note = {Accessed: 2022-02-17},
    year = 2021
}

@misc{cto2021interview,
    author = {{A container terminal operator in the German Bight}},
    title = {Conversation on Container Dwell times},
    year = 2021
}

@article{hartmann2004generating,
    title={Generating scenarios for simulation and optimization of container terminal logistics},
    author={Hartmann, S{\"o}nke},
    journal={{OR Spectrum}},
    volume={26},
    number={2},
    pages={171--192},
    year={2004},
    publisher={Springer},
    doi={10.1007/s00291-003-0150-6}
}

@online{macgregor2016containersecuring,
    author = {MacGregor},
    title = {{Container securing systems : Product catalogue}},
    howpublished = {\url{https://www.macgregor.com/globalassets/picturepark/imported-assets/65120.pdf}},
    note = {Accessed: 2022-01-26},
    year = 2016
}

@inproceedings{kastner2022conflowgen,
    author = {Kastner, Marvin and Grasse, Ole and Jahn, Carlos},
    title = {Container Flow Generation for Maritime Container Terminals},
    pages = {133 -- 143},
    booktitle = {Dynamics in Logistics. Proceedings of the 8th International Conference LDIC 2022, Bremen, Germany},
    eventdate = {2022-02-23/2022-02-25},
    year = {2022},
    editor = {Freitag, Michael and Kinra, Aseem and Kotzab, Herbert and Megow, Nicole},
    publisher = {Springer},
    address = {Cham, Switzerland},
    doi = {https://doi.org/10.1007/978-3-031-05359-7_11},
}

@article{exposito2012marshalling,
    title = {Pre-Marshalling Problem: Heuristic solution method and instances generator},
    journal = {Expert Systems with Applications},
    volume = {39},
    number = {9},
    pages = {8337-8349},
    year = {2012},
    issn = {0957-4174},
    doi = {10.1016/j.eswa.2012.01.187},
    author = {Expósito-Izquierdo, Christopher and Melián-Batista, Belén and Moreno-Vega, Marcos}
}

@online{exposito2012marshalling-software,
    title = {Bay Generator},
    howpublished = {\url{https://sites.google.com/site/gciports/premarshalling-problem/bay-generator}},
    note = {Accessed: 2022-07-20},
    year = {2022}
}

@Article{briskorn2019generator,
    author={Briskorn, Dirk and Jaehn, Florian and Wiehl, Andreas},
    title={A generator for test instances of scheduling problems concerning cranes in transshipment terminals},
    journal={OR Spectrum},
    year={2019},
    month={Mar},
    day={01},
    volume={41},
    number={1},
    pages={45--69},
    issn={1436-6304},
    doi={10.1007/s00291-018-0529-z},
}

@article{meisel2011unified,
    title = {A unified approach for the evaluation of quay crane scheduling models and algorithms},
    journal = {Computers \& Operations Research},
    volume = {38},
    number = {3},
    pages = {683-693},
    year = {2011},
    issn = {0305-0548},
    doi = {10.1016/j.cor.2010.08.001},
    author = {Meisel, Frank and Bierwirth, Christian}
}

@online{meisel2011unified-software,
    author = {Meisel, Frank},
    title = {{QCSPgen} - A Benchmark Generator for Quay Crane Scheduling Problems},
    howpublished = {\url{https://prodlog.wiwi.uni-halle.de/forschung/research_data/qcspgen/}},
    note = {Accessed: 2022-07-20},
    year = {2022}
}


text:
package ws

import (
	"net/http"

	"github.com/williamlian/simple-go-pubsub.git/pubsub"
)

var pubsubSingle pubsub.PubSub
var pubWsSingle http.Handler
var subWsSingle http.Handler

var _instantiated bool = false

// GetHandlers returns a publish http handler and the subscription websocker handler
func GetHandlers() (pub http.Handler, sub http.Handler) {
	if !_instantiated {
		pubsubSingle = pubsub.NewPubSub()
		pubWsSingle = &pubHandler{}
		subWsSingle = &subHandler{}
		_instantiated = true
	}
	return pubWsSingle, subWsSingle
}

repository: williamlian/simple-go-pubsub

repo_name: williamlian/simple-go-pubsub