Related Research Articles
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.
Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph algorithms, including Tarjan's strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.
A distributed hash table (DHT) is a distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. Keys are unique identifiers which map to particular values, which in turn can be anything from addresses, to documents, to arbitrary data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.
Borůvka's algorithm is a greedy algorithm for finding a minimum spanning tree in a graph, or a minimum spanning forest in the case of a graph that is not connected.
In computing, Chord is a protocol and algorithm for a peer-to-peer distributed hash table. A distributed hash table stores key-value pairs by assigning keys to different computers ; a node will store the values for all the keys for which it is responsible. Chord specifies how keys are assigned to nodes, and how a node can discover the value for a given key by first locating the node responsible for that key.
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output are random variables.
In computer science, consistent hashing is a special kind of hashing technique such that when a hash table is resized, only keys need to be remapped on average where is the number of keys and is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.
Douglass Read Cutting is a software designer, advocate, and creator of open-source search technology. He founded two technology projects, Lucene, and Nutch, with Mike Cafarella. Both projects are now managed through the Apache Software Foundation. Cutting and Cafarella are also the co-founders of Apache Hadoop.
The William O. Baker Award for Initiatives in Research, previously the NAS Award for Initiatives in Research, is awarded annually by the National Academy of Sciences "to recognize innovative young scientists and to encourage research likely to lead toward new capabilities for human benefit. The award is to be given to a citizen of the United States, preferably no older than 35 years of age. The field of presentation rotates among the physical sciences, engineering, and mathematics."
Learning to rank or machine-learned ranking (MLR) is the application of machine learning, typically supervised, semi-supervised or reinforcement learning, in the construction of ranking models for information retrieval systems. Training data consists of lists of items with some partial order specified between items in each list. This order is typically induced by giving a numerical or ordinal score or a binary judgment for each item. The goal of constructing the ranking model is to rank new, unseen lists in a similar way to rankings in the training data.
Hari Balakrishnan is the Fujitsu Professor of Computer Science and Artificial Intelligence in the Department of Electrical Engineering and Computer Science at MIT, and the Co-founder and CTO at Cambridge Mobile Telematics.
Ion Stoica is a Romanian-American computer scientist specializing in distributed systems, cloud computing and computer networking. He is a professor of computer science at the University of California, Berkeley and co-director of AMPLab. He co-founded Conviva and Databricks with other original developers of Apache Spark.
Anna R. Karlin is an American computer scientist, the Microsoft Professor of Computer Science & Engineering at the University of Washington.
Marinus Frans (Frans) Kaashoek is a Dutch computer scientist, entrepreneur, and Charles Piper Professor at the Massachusetts Institute of Technology.
Monika Henzinger is a German computer scientist, and is a former director of research at Google. She is currently a professor at the University of Vienna. Her expertise is mainly on algorithms with a focus on data structures, algorithmic game theory, information retrieval, search algorithms and Web data mining. She is married to Thomas Henzinger and has three children.
Valerie King is an American and Canadian computer scientist who works as a professor at the University of Victoria. Her research concerns the design and analysis of algorithms; her work has included results on maximum flow and dynamic graph algorithms, and played a role in the expected linear time MST algorithm of Karger et al.
ChengXiang Zhai is a computer scientist. He is a Donald Biggar Willett Professor in Engineering in the Department of Computer Science at the University of Illinois at Urbana-Champaign.
A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice. Galactic algorithms were so named by Richard Lipton and Ken Regan, because they will never be used on any data sets on Earth.
Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
References
- ↑ David Karger publications indexed by Google Scholar
- 1 2 David Karger at the Mathematics Genealogy Project
- ↑ "David Karger CSAIL" . Retrieved 13 March 2011.
- ↑ Karger, David. "Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm". Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993.
- ↑ Karger, D. R.; Klein, P. N.; Tarjan, R. E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321. CiteSeerX 10.1.1.39.9012 . doi:10.1145/201019.201022. S2CID 832583.
- ↑ Stoica, I.; Morris, R.; Karger, D.; Kaashoek, M. F.; Balakrishnan, H. (2001). "Chord: A scalable peer-to-peer lookup service for internet applications" (PDF). ACM SIGCOMM Computer Communication Review. 31 (4): 149. doi:10.1145/964723.383071.
- ↑ Cutting, D. R.; Karger, D. R.; Pedersen, J. O.; Tukey, J. W. (1992). "Scatter/Gather: a cluster-based approach to browsing large document collections". Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval - SIGIR '92. p. 318. CiteSeerX 10.1.1.34.6746 . doi:10.1145/133160.133214. ISBN 978-0897915236. S2CID 373655.
- ↑ "David Karger". Awards Home. Association for Computing Machinery . Retrieved 2021-01-23.
- ↑ "A.W. Tucker Prize - Past Winners". Mathematical Optimization Society Prizes. Mathematical Optimization Society.
- ↑ "William O. Baker Award for Initiatives in Research Recipients". About the William O. Baker Award for Initiatives in Research. National Academy of Sciences.
- ↑ "About Allegra". Archived from the original on 24 June 2011. Retrieved 13 March 2011.
