978 citations
- University of CopenhagenDK77 papers
- Technical University of DenmarkDK18 papers
- Institute for Scientific InterchangeIT17 papers
- Complexity Science HubAT16 papers
- Institut national de recherche en sciences et technologies du numériqueFR13 papers
- University College CopenhagenDK12 papers
- University of OxfordGB12 papers
- Aarhus UniversityDK11 papers
- Aalborg UniversityDK10 papers
- Chalmers University of TechnologySE10 papers
- ETH ZurichCH9 papers
- Google (United States)US9 papers
4 papers · 2 filters
RAM-Efficient External Memory Sorting
Lars Arge, Mikkel Thorup
In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are move…
The Input/Output Complexity of Triangle Enumeration
Rasmus Pagh, Francesco Silvestri
We consider the well-known problem of enumerating all triangles of an undirected graph. Our focus is on determining the input/output (I/O) complexity of this problem. Let be th…
How to Approximate A Set Without Knowing Its Size In Advance
Rasmus Pagh, Gil Segev, Udi Wieder
The dynamic approximate membership problem asks to represent a set S of size n, whose elements are provided in an on-line fashion, supporting membership queries without false negat…
Bottom-k and Priority Sampling, Set Similarity and Subset Sums with Minimal Independence
Mikkel Thorup
We consider bottom-k sampling for a set X, picking a sample S_k(X) consisting of the k elements that are smallest according to a given hash function h. With this sample we can esti…