Search for: All records | NSF Public Access

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees

https://doi.org/10.1137/1.9781611977714.8

Schiefer, Nicholas; Chen, Justin Y; Indyk, Piotr; Narayanan, Shyam; Silwal, Sandeep; Wagner, Tal (January 2023, SIAM Conference on Applied and Computational Discrete Algorithms)

An ε-approximate quantile sketch over a stream of n inputs approximates the rank of any query point q—that is, the number of input points less than q—up to an additive error of εn, generally with some probability of at least 1−1/ poly(n), while consuming o(n) space. While the celebrated KLL sketch of Karnin, Lang, and Liberty achieves a provably optimal quantile approximation algorithm over worst-case streams, the approximations it achieves in practice are often far from optimal. Indeed, the most commonly used technique in practice is Dunning’s t-digest, which often achieves much better approximations than KLL on realworld data but is known to have arbitrarily large errors in the worst case. We apply interpolation techniques to the streaming quantiles problem to attempt to achieve better approximations on real-world data sets than KLL while maintaining similar guarantees in the worst case.
more » « less
Full Text Available
Merge what you can, fork what you can't: managing data integrity in local-first software

https://doi.org/10.1145/3517209.3524041

Schiefer, Nicholas; Litt, Geoffrey; Jackson, Daniel (April 2022, Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data)

In a local-first architecture that prioritizes availability in the presence of network partitions, there is a tension between two goals: merging concurrent changes without user intervention and maintaining data integrity constraints. We propose a synchronization model called forking histories which satisfies both goals in an unconventional way. In the case of conflicting writes, the model exposes multiple event histories that users can see and edit rather than converging to a single state. This allows integrity constraints to be maintained within each history while giving users flexibility in deciding when to manually reconcile conflicts. We describe a class of applications for which these integrity constraints are particularly important and propose a design for a system that implements this model.
more » « less
Full Text Available
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

Aamand, Anders; Chen, Justin Y; Indyk, Piotr; Narayanan, Shyam; Rubinfeld, Ronitt; Schiefer, Nicholas; Silwal, Sandeep; Wagner, Tal (January 2022, Conference on Neural Information Processing Systems)

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the “combine” function of size polynomial or even exponential in the number of graph nodes n, as well as feature vectors of length linear in n. We present an improved simulation of the WL test on GNNs with exponentially lower complexity. In particular, the neural network implementing the combine function in each node has only polylog(n) parameters, and the feature vectors exchanged by the nodes of GNN consists of only O(log n) bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.
more » « less
Full Text Available