betaFeedback

WorksComputer Science

Instance-Optimality of Single-Pair Personalized PageRank

Abstract

We consider discounted random walks in a directed simple graph G=(V,E)G=(V,E). Such a walk terminates at each step with a constant probability α∈(0,1)α\in (0,1) and otherwise continues to a uniform random out-neighbor. Given a pair (s,t)∈V2(s,t)\in V^2, we denote by π(s,t)π(s,t) the probability of such a discounted random walk starting at ss terminates at tt. This probability is referred to as the Personalized PageRank (PPR) of tt with respect to ss. The problem of estimating π(s,t)π(s,t) within a constant multiplicative factor with constant success probability for a given vertex pair (s,t)(s,t) is called the single-pair PPR estimation problem. We investigate the instance-optimality of single-pair PPR estimation in directed graphs. We present a new algorithm that aims at instance-optimal running time up to polylogarithmic factors. In other words, no correct algorithm can run faster than our algorithm on any valid graph by more than a polylogarithmic factor. We show that our algorithm is instance-optimal in the standard adjacency-list query model if nn is not known (as is often the case for most of the large networks to which PPR is applied). When nn is known, our algorithm is still instance-optimal for sparse graphs. For denser graphs, when nn is known, we show that no algorithm can achieve general instance-optimality. For the multiplicative approximation of PPR, we also improve the worst-case complexity from O(mnlog⁡n)O(mn\log n) to the near-optimal O(mlog⁡n)O(m\log n). This is not only for the single-pair discussed above, but also for the single-source and single-target variants of the PPR estimation problem.

Introduction

Random walks in directed graphs is an algorithmic building block in modern network analysis. One important type is the discounted random walk, where at each step, the walk either terminates with some probability α∈(0,1)\alpha\in(0,1), or moves to a uniformly random out-neighbor with probability 1−α1-\alpha. For simplicity, we assume that every vertex has at least one out-neighbor. This assumption can be easily satisfied by adding a self-loop to each dangling vertex. Following previous works [LBGC14, WYX+17, BPP23, WWWY24, TW26], we also assume that α\alpha is a constant throughout the paper.

Let π(s,t)\pi(s,t) denote the probability that a discounted random walk starting from vertex ss terminates at vertex tt. This probability is referred to as the Personalized PageRank (PPR) of tt with respect to ss. The notion of PPR was introduced by the co-founders of Google in [BP98, PBMW98] for personalized web search and has since become a widely used measure of node proximity, finding various applications in graph analysis and learning [3 LSK+11, BL11, KBG19, BKP+20a, EMP+22, WCL24]. The “Google” papers [BP98, PBMW98] also introduced PageRank for global webpage ranking. The PageRank π(t)\pi(t) for a vertex tt is defined as the average of the PPR values π(s,t)\pi(s,t) over all vertices s∈Vs \in V, i.e., π(t)=∑s∈Vπ(s,t)/n\pi(t) = \sum_{s \in V} \pi(s,t)/n, where nn is the number of vertices in the graph. Thus, by definition, an algorithm for estimating PPR π(s,t)\pi(s,t) can be extended to estimate the PageRank π(t)\pi(t) by adding a pseudo vertex s∗s^* with outgoing edges to all vertices in the graph and estimating π(s∗,t)\pi(s^*,t).

In this paper, we study the single-pair PPR problem, which aims to estimate π(s,t)\pi(s,t) for a given source vertex ss and a given target vertex tt in a directed graph G=(V,E)G = (V,E) within a constant multiplicative factor with constant success probability. This problem and its variants have received considerable attention over the past decades [LBGC14, LBG16, WYX+17, BPP18, BPP23, WWWY24, TWWY26, TW26], with applications in diverse areas, including web search [PBMW98, GP07], recommender systems [GGL+13], node embedding [YW19], graph neural networks [BKP+20b], and many others [Gle15, YWW+24]. There is also a line of work that studies this problem and its variants on undirected graphs [LBG15, Wan24, BJ26, CWY26, LXYZ26], but in this paper, we consider only directed graphs.

The focus of this paper is to find an instance-optimal algorithm for the single-pair PPR problem, that is, an algorithm whose running time is close to optimal on every input graph among all correct algorithms, or rather probabilistically correct since most algorithms for PPR are randomized.

Instance-Optimality

Traditionally, theory of computing has focused on worst-case complexity, but algorithms that are worst-case efficient may perform very poorly on easy instances encountered in practice, and it is their performance on practical instances that determines actual computational costs and energy consumption. This has motivated research on designing algorithms that are average-case efficient or perform well on specific classes of instances, e.g., power-law graphs or sparse graphs. However, it is often difficult to determine which classes of instances or graph parameters are most relevant (e.g., whether sparse or dense graphs are more important), as the answer depends on the applications, which may evolve over time. An ideal solution would be to design an algorithm that achieves optimal running time on every possible instance, thereby covering all instances encountered in practice. Such an algorithm is called an instance-optimal algorithm.

A beautiful illustration of the advantage of an instance-optimal algorithm over a worst-case optimal algorithm is the shortest-path problem: What is the fastest way to get from AA to BB? Dijkstra’s algorithm [Dij59], Problem 2, stated for single-pair, not single-source) with a priority queue establishes the Θ~(m)\widetilde{\Theta}(m) worst-case complexity of this problem assuming non-negative weights, with many great works devoted to understanding the logarithmic factor hidden by the Θ~\widetilde{\Theta} notation (see [DMM+25, DMSY26] and the references therein). However, individual instances can be much easier. As an example, imagine that you want to go to Rome. This is easy because all roads lead to Rome. More mathematically, think of an undirected star graph with Rome in the center: Dijkstra will find the center from any node in constant time. However, when you want to go back home from Rome after the party, Dijkstra may lead you to explore the whole graph. Bidirectional Dijkstra will be fast in both directions, and it is, in fact, instance-optimal within a logarithmic factor for positively weighted multigraphs [HHR+25].

Instance-optimality is much stronger than worst-case optimality or average-case optimality, since it requires the algorithm to be the best, or close to best, among all good algorithms on every instance, rather than merely excel in the worst case or on average. It is therefore regarded as the ultimate notion of optimality [CL16, ABC17]. Here, a good (randomized) algorithm refers to one that is (probabilistically) correct on every valid instance. When we say that an algorithm is instance-optimal, we mean that its running time on every instance is at most a small factor larger than that of the fastest good algorithm on that instance, e.g., a polylogarithmic factor when the running times are polynomial. A good algorithms may be instance-smart in the sense that it is tuned to be fast on a particular instance (but may be slow on other instances). This subsume algorithms that receive good but not fully trusted advice (e.g., advice from AI [MV22]). But the instance-smart algorithm must verify that its answer is probabilistically correct, so that it is not fooled when given an input that is not the instance for which it was tuned. Thus, an algorithm that simply outputs an answer without verifying its correctness is not considered a competitor of instance-optimal algorithm.

For most problems, instance-optimal algorithms do not exist [2 HHR+24]. Some positive examples are known, e.g., in quantity estimation [DKLR00], database aggregation [FLN03], sequential estimation [VV16, DLSV23, NRTT24], computational geometry [2 dBvR+25], distribution testing and learning [VV17, VV20, BCW25], contextual bandits [LRN+22], and the above-mentioned shortest-path problem with positive weights [HHR+25, BJT+26a]. Additionally, [HHR+24] establishes universal optimality for a new priority-queue in Dijkstra’s single-source shortest paths problem. The notion of universal optimality is strictly weaker than instance-optimality but still substantially stronger than worst-case optimality. The most relevant work is a recent paper that investigates the instance-optimality of estimating a vertex’s PageRank [TW26]. We will return to this work and its connection to our paper later.

Personalized PageRank (PPR)

As mentioned earlier, in this paper, we study the single-pair Personalized PageRank (PPR) problem and investigate its instance-optimality. Recall that the problem is to estimate π(s,t)\pi(s,t) with constant relative error and constant success probability, given a source vertex ss and a target vertex tt in a directed graph GG. Some previous works also introduce an approximation threshold parameter δ∈[0,1]\delta\in[0,1] and only require an estimate of π(s,t)\pi(s,t) when π(s,t)>δ\pi(s,t) > \delta. We note that π(s,t)\pi(s,t) can be as small as 1/nΩ(n)1/n^{\Omega(n)} (we shall see example in Figure 3). For our own algorithms, we will at first not parameterize the problem by δ\delta, that is, we consider δ=0\delta= 0, but we will later show that our instance-optimality results extend to the setting where such an approximation threshold δ\delta is given.

Figure 3. Illustrative example where π(s,t)\pi(s,t) is extremely small.

We will now discuss some of the previous work on this problem, most of which involves δ\delta.

Worst-case complexity. Let nn and mm denote the number of vertices and edges in GG, respectively. The best-known worst-case complexity is O(min⁡{1/δ,mlog⁡(1/δ)})O(\min\{1/\delta, m\log(1/\delta)\}), obtained simply by combining Monte Carlo sampling and the power method. Specifically, Monte Carlo sampling estimates π(s,t)\pi(s,t) in O(1/δ)O(1/\delta) time by generating O(1/δ)O(1/\delta) random walks from the source vertex ss and using the fraction of walks that terminate at tt as the estimate of π(s,t)\pi(s,t). The power method, introduced in the seminal paper that proposes PPR and PageRank [PBMW98], iteratively applies the definition equation of PPR: πs=(1−α)Pπs+α1s\boldsymbol{\pi}_s = (1-\alpha)\mathbf{P}\boldsymbol{\pi}_s + \alpha\mathbf{1}_s, where πs\boldsymbol{\pi}_s is an nn-dimensional PPR vector with πs[t]=π(s,t)\boldsymbol{\pi}_s[t] = \pi(s,t), P\mathbf{P} is the random-walk transition matrix, and 1s\mathbf{1}_s is an nn-dimensional one-hot vector with only 1[s]=1\mathbf{1}[s] = 1. Each iteration takes O(m)O(m) time for computing Pπs\mathbf{P}\boldsymbol{\pi}_s as it touches all edges in the graph. The geometric convergence rate of (1−α)(1-\alpha) ensures that after log⁡(1−α)δ=O(log⁡(1/δ))\log_{(1-\alpha)}\delta= O(\log(1/\delta)) iterations, the absolute error falls below δ\delta, thus yielding the O(mlog⁡(1/δ))O(m \log(1/\delta)) runtime.3

The O(min⁡{1/δ,mlog⁡(1/δ)})O(\min\{1/\delta, m \log(1/\delta)\}) upper bound also holds for the single-source PPR problem, that is, estimating π(s,t)\pi(s,t) for all possible targets t∈Vt \in V, since both Monte Carlo sampling and the power method can estimate π(s,t)\pi(s,t) simultaneously for all targets t∈Vt \in V. One might hope that the single-pair complexity should be smaller than that of the single-source. However, our unpublished manuscript [BJT+25] establishes a tight Ω(min⁡{1/δ,m})\Omega(\min\{1/\delta,m\}) lower bound for both the single-pair and single-source PPR problems. Therefore, in the worst case, solving the single-pair PPR problem requires as much time as solving the single-source problem.

Better algorithms for some instances. Analogous to the aforementioned shortest path problem where Dijkstras algorithm is worst-case optimal yet other algorithms, such as bidirectional Dijkstra, can be much faster on particular instances, previous work on single-pair PPR has also sought to improve performance on individual instances despite the worst-case lower bound. This includes [DKLR00], which proposes an adaptive Monte Carlo sampling method that estimates π(s,t)\pi(s,t) in O(min⁡{1/δ,1/π(s,t)})O(\min\{1/\delta, 1/\pi(s,t)\}) time, which is faster on instances where π(s,t)>δ\pi(s,t) > \delta.

Another line of work [LBGC14, LBG16] seeks to go beyond worst-case complexity by considering the average-case complexity: complexity of estimating π(s,t)\pi(s,t) for an arbitrary source ss and a uniformly random target t∈Vt \in V. [LBG16] proposes a bidirectional search algorithm, which we refer to as BiPPR. The BiPPR algorithm combines Monte Carlo sampling with a so-called backward push method [1], which deterministically propagates random-walk probability mass backward from the target vertex tt along incoming edges, step by step. For this bidirectional BiPPR, the worst-case running time is still O(min⁡{1/δ,mlog⁡(1/δ)})O(\min\{1/\delta, m \log(1/\delta)\}), but [LBG16] proves that it achieves an average-case complexity of O((m/n)/δ)O(\sqrt{(m/n)/\delta}) [LBG16], which is better than the aforementioned worst-case complexity of O(min⁡{1/δ,mlog⁡(1/δ)})O(\min\{1/\delta, m \log(1/\delta)\}) when δ>n/m\delta> n/m.

Another set of research [BM08, BPP23, WWWY24, TWWY26, TW26] studies the PageRank estimation problem: estimating the PageRank π(t)\pi(t) of a given target vertex tt. Recall that an algorithm for estimating single-pair PPR π(s,t)\pi(s,t) for a given source ss and a given target tt can be trivially extended to estimate the PageRank π(t)=∑s∈Vπ(s,t)/n\pi(t) = \sum_{s \in V} \pi(s,t)/n for a given target tt: adding a pseudo vertex s∗s^* with outgoing edges to all vertices in the graph and estimating π(s∗,t)\pi(s^*,t) for the given target tt. [WWWY24] revisits the above-mentioned BiPPR method and shows that it solves the PageRank estimation problem in O(n1/2m1/4)O(n^{1/2}m^{1/4}) time and that this bound is already worst-case optimal. Recently, [TW26] showed that the adaptive variant of this BiPPR method is even instance-optimal for PageRank estimation on a class of graphs G∗\mathcal{G}^* in which each graph has at most a polylogarithmic number of vertices with in- or out-degree at least (1−o(1))n(1-o(1))n. The graph class G∗\mathcal{G}^* contains almost all graphs including all sparse graphs.

For all that is known, it could be that BiPPR was always instance-optimal for PPR, but we shall see that it can be off by a factor Ω(m/log⁡n)\Omega(m/\log n) even when π(s,t)=Ω(1/m)\pi(s,t) = \Omega(1/m).

Main contributions

In this paper, we design a simple algorithm called TriPPR for the single-pair PPR problem: estimating π(s,t)\pi(s,t) for a given ss and tt with constant relative error and constant success probability. Like in many previous works, we can also benefit from an approximation threshold parameter δ∈[0,1]\delta\in[0,1] where we only require an estimate of π(s,t)\pi(s,t) when π(s,t)>δ\pi(s,t) > \delta. We show that our new algorithm instance-optimal if nn is not known. When nn is known, our algorithm is still instance-optimal for sparse graphs with m=O~(n)m = \widetilde{O}(n). For denser graphs, when nn is known, we show that no algorithm can achieve general instance-optimality.

As we discuss below in § 1.4, not knowing nn is a common case for some of the large networks for which we want to compute PPR values. Having an algorithm not knowing nn is thus very relevant.

For the multiplicative approximation of PPR, that is, δ=0\delta= 0, we also improve the worst-case complexity from O(mnlog⁡n)O(mn \log n) [PBMW98] to the near-optimal O(mlog⁡n)O(m \log n). This improvement is not only for the single-pair discussed above, but also for single-source and single-target.

Model

For our algorithms and running-time upper bounds we assume the standard unit-cost RAM model with word-size Θ(log⁡n)\Theta(\log n). This includes arithmetic operations on floating-point numbers with O(log⁡n)O(\log n)-bit exponent and mantissa.

Our lower bounds are proved in the adjacency-list query model for sublinear graph algorithms. The latter supports in- and out-degree queries indeg⁡(v)\operatorname{indeg}(v) and outdeg⁡(v)\operatorname{outdeg}(v), which return the in- and out-degree of a vertex vv, respectively, as well as in- and out-neighbor queries in⁡(v,i)\operatorname{in}(v,i) and out⁡(v,i)\operatorname{out}(v,i), which return the ii-th in- and out-neighbor of vv, respectively. Each query incurs unit cost. Basically, we are only given direct access to ss and tt in a large unknown network. The only way to access other nodes is to follow in- and out-edges from vertices already visited. We do not have any other global information on the network. In particular, we do not necessarily know the number nn of vertices in the graph. Our TriPPR algorithm does not use knowledge of nn. We consider its instance-optimality both when nn is known and when nn is not known.

The above kind of limited local access without knowledge of nn aligns with the graph queries provided by application programming interfaces (APIs) for large real-world networks. For example, consider the World Wide Web. No single entity owns or maintains the entire web, and there is no universal API that provides the exact number of existing web pages. Similarly, large-scale social networks such as Facebook do not provide an API operation for querying the total number of vertices nn [7].

This also reflects the capabilities of APIs for large real-world networks. For example, Google has explicitly acknowledged that it does not know the exact number of unique pages on the web [5], noting that the web is too large for its crawlers to discover every publicly accessible URL [Goo26]. Similarly, consider large-scale social networks such as Facebook. Maintaining an exact, globally consistent vertex count in Facebook’s massive, continuously evolving social graph could require substantial communication and synchronization overhead [LPD+25].

We remark that prior work on PageRank estimation, such as [ALN07, BBCT12, BBCT14, BPP23, WWWY24, TW26], also introduces a query called JUMP(), which returns a uniformly random vertex in the graph. This JUMP query is important for PageRank estimation as it because, by definition, the PageRank score π(t)\pi(t) of a vertex tt is the average of π(s,t)\pi(s,t) over all source vertices ss in the graph, i.e., π(t)=E[π(JUMP⁡(),t)]\pi(t) = \mathbb{E}[\pi(\operatorname{JUMP}(),t)]. [BM08, BPP13] show that without the JUMP query, no sublinear-time algorithm exists for PageRank estimation. In contrast, the JUMP query is not necessary for PPR estimation. Prior work on PPR estimation, whether for the single-pair, single-source, or single-target problem, e.g., [LBG16, WYX+17, ABC+08], does not assume access to such a query, and neither do we. Indeed, a JUMP-query that is guaranteed to finds any vertex with probability close to 1/n1/n has issues similar to a query on nn, e.g., it is not available in an an API like [7]. Thus, when we prove instance optimality not knowing nn, we also assume that there is no JUMP query. Observe that when we reduce PageRank to PPR, we introduced a node s∗s^* with out-edges to all other nodes, so going to a random out-neighbor from s∗s^{*} is the same as a Jump, except that we may not have the knowledge that dout(s∗)=nd_{\mathrm{out}}(s^{*})=n.

Note that our lower-bounds are information theoretic based on query complexity. In particular, they can never go above Ω(m)\Omega(m) if we read the whole graph. For contrast, our upper bounds are time bounds, and our algorithms may do multiple operations on the same vertices and edges.

Technical Perspective

The design of TriPPR is motivated by two challenges. First, existing PPR algorithms can spend substantial time exploring parts of a graph that an instance-smart algorithm can handle much more efficiently. We explain how TriPPR addresses this by combining forward push, backward push, and Monte Carlo sampling. Second, existing pushing algorithms can become very expensive when estimating extremely small PPR values. We address this problem with a vertex-freezing technique that limits the amount of work spent on each vertex. Finally, we consider what changes when the number of vertices nn is known. We explain why this additional information makes instance-optimality impossible, and then provide a more refined characterization of the achievable instance-optimality ratio, showing in particular that TriPPR remains instance-optimal for sparse graphs and a much broader class of locally solvable instances.

Issues with Existing Algorithms

Before inventing a new algorithm for single-pair PPR estimation, let us first ask if the currently best algorithm BiPPR could be instance optimal. We recall that it is worst-case optimal within a factor O(log⁡1/δ)O(\log1/\delta), and we know from [TW26] that it is instance-optimal for the special case of PageRank estimation.

The example instance of Figure 1 shows that BiPPR may be very far from instance-optimal. In this example, BiPPR spends Ω(m)\Omega(m) time while the instance can be solved by an instance-smart algorithm in O(log⁡n)O(\log n) time.

Figure 1. Hard instances for single-pair PPR estimation, on which an instance-smart algorithm takes O(log⁡n)O(\log n) time, while the previously best BiPPR algorithm [LBG16] takes O(m)O(m) time, and pure Monte Carlo sampling takes ω(mn)\omega(mn) time.

The toy graph in Figure 1 consists of a binary tree of depth log⁡m\log m connecting the source vertex ss to a vertex uu, a complete bipartite graph with m\sqrt{m} vertices on each side connecting uu to another vertex vv, and a depth-one tree rooted at vv with nn leaves (the getting-home-from-Rome example mentioned earlier), one of which is the target vertex tt. We note that in this graph,

π(s,t)=π(s,u)π(u,v)π(v,t)/α2=((1−α)/2)log⁡m(1−α)3((1−α)/n)α=o(1/(nm))\pi(s,t)=\pi(s,u)\pi(u,v)\pi(v,t)/\alpha^{2}=((1-\alpha)/2)^{\log m}(1-\alpha)^{3}((1-\alpha)/n)\alpha=o(1/(nm))

To estimate π(s,t)\pi(s,t), a pure forward Monte Carlo sampling of discounted random walks from ss needs ω(nm)\omega(nm) samples since π(s,t)=o(1/(mn))\pi(s,t) = o(1/(mn)); otherwise it will not reach tt with constant probability.

The BiPPR method requires Ω(m)\Omega(m) time as it combines Monte Carlo sampling from ss and backward push from tt. One of them, or both, must reach uu. To reach uu with constant probability, the Monte Carlo sampling needs Ω(1/π(s,u))=ω(m)\Omega(1/\pi(s,u)) = \omega(m) samples. The backward-push method [1] deterministically propagates random-walk probability mass backward from the target vertex tt along incoming edges, step by step. To reach uu from tt, it will explore the Ω(m)\Omega(m) edges in the subgraph between uu and vv. It follows that BiPPR takes Ω(m)\Omega(m) time on this instance.

In contrast, an instance-smart algorithm can first completely explore the O(log⁡m)O(\log m)-sized subgraph between ss and uu and ascertain that any path from ss leaving this subgraph must pass through uu. Having explored this subgraph completely, it will know π(s,u)\pi(s,u), but only costing O(log⁡m)O(\log m) time. Likewise, since (v,t)(v,t) is the only edge entering tt, it knows that every ss-tt path must pass through vv and that π(v,t)=(1−α)/dout(v)=(1−α)/n\pi(v,t) = (1-\alpha)/d_{\mathrm{out}}(v) = (1-\alpha)/n. It remains to estimate π(u,v)\pi(u,v), which can be done by Monte Carlo sampling in constant time; for all paths in the middle subgraph lead from uu to vv in three hops, so π(u,v)=(1−α)3=Ω(1)\pi(u,v) = (1-\alpha)^3 = \Omega(1).

Basic Idea for the TriPPR Algorithm

Our new TriPPR algorithm is motivated by examples such as the one in Figure 1. It overcomes the limitations of Algorithm 3 by using a three-component algorithm, a bit like the instance-smart algorithm mentioned above: forward push from ss, backward push from tt, and Monte Carlo sampling.

Forward push is the counterpart to backward push and was proposed even earlier [3]. Like backward push, it deterministically propagates random-walk probability mass step by step through the graph, but along outgoing edges rather than incoming edges. Looking again at Figure 1, forward push estimates π(s,u)\pi(s,u) in only O(log⁡n)O(\log n) time, and backward push estimates π(v,t)\pi(v,t) in constant time. Monte Carlo sampling then estimates the probability of the intermediate walk from uu to vv, by sampling random walks from uu until one of them successfully terminates at vv, spending only constant time on the example. These three probability estimates then combine to estimate π(s,t)\pi(s,t).

References

  1. [1]Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, and Shang-Hua Teng. Local computation of PageRank contributions. Internet Mathematics, 5(1):23–45, 2008. doi:10.1080/15427951.2008.10129302.DOI
  2. [2]Peyman Afshani, Jérémy Barbay, and Timothy M. Chan. Instance-optimal geometric algorithms. J. ACM, 64(1):3:1–3:38, 2017. doi:10.1145/3046673.DOI
  3. [3]Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using PageRank vectors. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pages 475–486, 2006. doi:10.1109/FOCS.2006.44.DOI
  4. [4]Aesop. The fox and the grapes, 6th century BC. Perry Index 15.
  5. [5]Jesse Alpert and Nissan Hajaj. We knew the web was big... https://googleblog.blogspot.com/2008/07/we-knew-web-was-big.html, July 2008. Official Google Blog.
  6. [7]Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkateshwaran Venkataramani. TAO: facebook’s distributed data store for the social graph. In Andrew Birrell and Emin Gün Sirer, editors, Proceedings of the 2013 USENIX Annual Technical Conference, USENIX ATC 2013, San Jose, CA, USA, June 26–28, 2013, pages 49–60. USENIX Association, 2013. URL: https://www.usenix.org/conference/atc13/technical-sessions/presentation/bronson.

Paper details

vlnc:W_wbrpa42g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT Pro

View statement
Looking for related papers…
Contents