1,721,166 research outputs found
Fast and Powerful Hashing Using Tabulation (Invited Talk)
Get PDFRandomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees.
Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of c characters and we have precomputed character tables h_1, ... , h_q mapping characters to random hash values. A key x = (x_1 , ..., x_c) is hashed to h_1[x_1] + h_2[x_2] ... + h_c[x_c]. This scheme is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does
provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing.
Next we consider twisted tabulation where one character is "twisted" with some simple operations. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing.
Finally, we consider double tabulation where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size
proportional to that of the space consumed, double tabulation gives fully-random hashing.
While these tabulation schemes are all easy to implement and use, their analysis is not
Performance of estimated traffic matrices in traffic engineering
No full textWe consider the performance of estimated traffic matrices in traffic engineering. More precisely, we first optimize the routing in an IP backbone to minimize congestion with the estimated traffic matrix. We then test the performance of the resulting routing on the real traffic matrix.Matthew Roughan, Mikkel Thorup, Yin Zhan
Oracles for distances avoiding a failed node or link
No full textWe consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length of a shortest path from any given vertex x to another given vertex y avoiding an arbitrary vertex or edge. As a natural application, this problem models routing in networks subject to node or link failures. We describe a deterministic oracle with constant query time for this problem that uses O(n^2 log n) space, where n is the number of vertices in G. We also show that if we are willing to use Theta(n^2.5) space, we can reduce the preprocessing time by a factor of n^0.5 while maintaining constant query time. Our algorithms can find the shortest path avoiding a failed node or link in time proportional to the length of the path
Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)
No full text) Martin Farach 3 Mikkel Thorup y Department of Computer Science Department of Computer Science Rutgers University University of Copenhagen Piscataway, NJ 08855 2100 København Ø USA Denmark Abstract In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined as follows: given a set A and two rooted trees T 0 and T 1 leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of T 0 and T 1 to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with 2(n 2 ) nodes---and 2(n 2 ) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc p log n ) additive overhead. Applying the best bound for UWBM, we get an O(n 1:5 log n) algorithm for MAST. From ..
ENQUETE: Studenten, der ville vide, hvor staten var henne
Get PDFENQUETE: Mikkel Thorup: Studenten, der ville vide, hvor staten var henn
Anmeldelse af Demokratiets krise og de nye autokratier
No full textPeter Seeberg og Mikkel Thorup (red.), Demokratiets krise og de nye autokratier. Aarhus: Aarhus Universitetsforlag, 2020, 368 sider, 299,95 kr. (anmeldt af Palle Svensson
A Measurement-driven Analysis of Information Propagation in the Flickr Social Network
Get PDFWe thank Augustin Chaintreau, Anja Feldmann, Duncan Watts,
Divesh Srivastava, Rasmus Pagh, Mikkel Thorup, Juan Antonio
Navarro Pérez, Bryan Ford, Nuno Santos, Bimal Viswanath, Rose
Hoberman, and anonymous reviewers, for their valuable comments
Reconstructing the Tree of Life (Fitting Distances by Tree Metrics) (Invited Paper)
No full textWe consider the numerical taxonomy problem of fitting an S× S distance matrix D with a tree metric T. Here T is a weighted tree spanning S where the path lengths in T induce a metric on S. If there is a tree metric matching D exactly, then it is easily found. If there is no exact match, then for some k, we want to minimize the L_k norm of the errors, that is, pick T so as to minimize
‖D-T‖_k = (∑_{i,j ∈ S} |D(i,j)-T(i,j)|^k) ^{1/k}.
This problem was raised in biology in the 1960s for k = 1,2. The biological interpretation is that T represents a possible evolution behind the species in S matching some measured distances in D. Sometimes, it is required that T is an ultrametric, meaning that all species are at the same distance from the root.
An evolutionary tree induces a hierarchical classification of species and this is not just tied to biology. Medicine, ecology and linguistics are just some of the fields where this concept appears, and it is even an integral part of machine learning and data science. Fundamentally, if we can approximate distances with a tree, then they are much easier to reason about: many questions that are NP-hard for general metrics can be answered in linear time on tree metrics. In fact, humans have appreciated hierarchical classifications at least since Plato and Aristotle (350 BC).
The numerical taxonomy problem is important in practice and many heuristics have been proposed. In this talk we will review the basic algorithmic theory, results and techniques, for the problem, including the most recent result from FOCS'21 [Vincent Cohen-Addad et al., 2021]. They paint a varied landscape with big differences between different moments, and with some very nice open problems remaining.
- At STOC'93, Farach, Kannan, and Warnow [Martin Farach et al., 1995] proved that under L_∞, we can find the optimal ultrametric. Almost all other variants of the problem are APX-hard.
- At SODA'96, Agarwala, Bafna, Farach, Paterson, and Thorup [Richa Agarwala et al., 1999] showed that for any norm L_k, k ≥ 1, if the best ultrametric can be α-approximated, then the best tree metric can be 3α-approximated. In particular, this implied a 3-approximation for tree metrics under L_∞.
- At FOCS'05, Ailon and Charikar [Nir Ailon and Moses Charikar, 2011] showed that for any L_k, k ≥ 1, we can get an approximation factor of O(((log n)(log log n))^{1/k}) for both tree and ultrametrics. Their paper was focused on the L₁ norm, and they wrote "Determining whether an O(1) approximation can be obtained is a fascinating question".
- At FOCS'21, Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [Vincent Cohen-Addad et al., 2021] showed that indeed a constant factor is possible for L₁ for both tree and ultrametrics. This uses the special structure of L₁ in relation to hierarchies.
- The status of L_k is wide open for 1 < k < ∞. All we know is that the approximation factor is between Ω(1) and O((log n)(log log n))
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
No full textIn the dynamic all-pairs shortest path problem we wish to maintain information about distances in a weighted graph subject to dynamic operations such as edge insertions, edge deletions, and edge weight updates. The most efficient algorithms for this problem maintain a suitable superset of shortest paths in the graph. This superset retains information about the history of previous graph updates so as to avoid pathological situations where algorithms are continuously forced to rebuild large portions of their data structures. On the other hand, the set of maintained paths may grow too large, resulting in both prohibitive space consumption and inefficient updates. To circumvent this problem, the algorithms perform suitable path cleaning operations. In this paper, we implement and experiment with a recent efficient algorithm by Thorup, which differs from the previous algorithms mainly in the way path cleaning is done, and we carry out a thorough experimental investigation on known implementations of dynamic shortest path algorithms. Our experimental study puts the new results into perspective with respect to previous work and gives evidence that path cleaning, although crucial for the theoretical bounds, appears to be instead of very limited impact in practice. © Springer-Verlag Berlin Heidelberg 2006
Antiterrorisme som regeringsteknik
No full textTerrorisme, antiterrorisme, krigen mod terror, kontrol
- …
