This paper presents GraphJet, a new graph-based system for generating content recommendations at Twitter. As motivation, we trace the evolution of our formulation and approach to the graph recommendation problem, embodied in successive generations of systems. Two trends can be identified: supplementing batch with real-time processing and a broadening of the scope of recommendations from users to content. Both of these trends come together in Graph-Jet, an in-memory graph processing engine that maintains a real-time bipartite interaction graph between users and tweets. The storage engine implements a simple API, but one that is sufficiently expressive to support a range of recommendation algorithms based on random walks that we have refined over the years. Similar to Cassovary, a previous graph recommendation engine developed at Twitter, GraphJet assumes that the entire graph can be held in memory on a single server. The system organizes the interaction graph into temporally-partitioned index segments that hold adjacency lists. GraphJet is able to support rapid ingestion of edges while concurrently serving lookup queries through a combination of compact edge encoding and a dynamic memory allocation scheme that exploits power-law characteristics of the graph. Each GraphJet server ingests up to one million graph edges per second, and in steady state, computes up to 500 recommendations per second, which translates into several million edge read operations per second.

The problem of finding documents pertaining to a particular topic finds application in a variety of scenarios. Indeed, the demand for topically pertinent documents has led to myriad companies offering services to find and deliver them (perhaps along with sentiment analysis or clustering) to customers for any topics of interest. The methodologies used to uncover relevant documents range from manually curated keyword filters to trained classification models. Any serious topical analysis requires a sound understanding of key metrics behind the retrieval process, two of the most important being precision and recall. While precision can be easily and inexpensively measured by sampling from classified documents and utilizing (paid) human computation to mark incorrectly classified instances, it is not as straightforward to use the same approach for measuring recall. With most topics occurring relatively sparsely, an unbiased sampling approach becomes prohibitively expensive. In this paper, we introduce a recall measurement procedure requiring only relatively few human judgements. The technique makes use of pairs of sufficiently independent classifiers and the paper provides a detailed discussion of how such classifier pairs can be constructed in practice, with a focus on social media classifiers. We report the performance of the proposed method with simple keyword filters as well as with classifiers of progressive levels of complexity and show that under reasonable conditions, recall can be estimated to within 0.10 absolute error and 15% relative error, and often closer with a reduction of cost by a factor of as much as 1000x as compared with unbiased sampling.

We consider a problem faced by wireless base stations in which multiple requests to stream data must be accomodated while minimizing the amount of buffering time spent by clients. In our model, clients request content in discrete data chunks, but the base station is restricted in which clients can simultaneously be served data at certain rates. This limitation occurs frequently due to wireless connectivity and congestion issues in which some clients are difficult to reach from the base station, whereas others are more easily serviced. These constraints are represented by a set of admissible service rate vectors from which a scheduler at the base station must choose. We take a queuing theoretic approach to this decision problem and employ a stress alignment approach to ensure that maximal throughput from the data center to the clients is achieved. As a consequence, whenever it is possible to stabilize the backlog of requests from each client, we are able to do so. Numerical experiments show that among the variations of this scheduling algorithm, we can choose parameters to vary the priority levels of different clients and even induce dependencies between service rates of different clients.

We examine the problem of tracking the states of a collection of systems over a finite horizon in a power limited scenario. Specifically, each system has a sensor which can track a property of interest and has a fixed budget with which to make measurements and communicate to a fusion center. The state at each system varies independently according to a Markov model and the transitions between different states occur according known transition matrices. Different systems can have vastly different state evolution statistics. At each time step, the fusion center can request an update from any number of the systems, subject to the constraint that the corresponding sensor has not exhausted its budget to do so. These measurement updates are expensive and hence resource limited. After the fusion center receives all updates, it must estimate the state at each system with minimum error. We give an optimal policy for the fusion center to request updates from each sensor and also provide an optimal policy for the fusion center to allocate the measurement budget to each sensor before deployment, given the transition matrices corresponding to each system.

We consider the problem of scheduling packets in an input queued switch with a focus on processing streamed multimedia data. In such applications, packets arrive with hard service deadlines; after the deadline for a packet has passed, it is no longer useful and does not get delivered - it is dropped. We seek policies to minimize the number of late packets, which are then dropped. The problem is formulated in a Dynamic Programming framework and shown to be intractable. The formulation is contrasted to the related crossbar switch scheduling problem, with an emphasis on the fact that we have a different objective function. A simplified probabilistic version of the streaming problem is used as motivation for a heuristic solution. Finally, we present results from a simulation in which a simple heuristic based on weighting queues according to the deadline of the leading packet consistently outperforms the well-known maximum weight matching (MWM) algorithm.

We examine the problem of fault detection in networked computing systems and highlight the tradeoff between diagnosing/reacting to potentially harmful real-time events and minimizing the number of times the system is reset or scanned for malicious activity. The various health states of a system are modeled as states in a Markov chain, and we use a model fitting approach to estimate the transitions between these states. We proceed by considering a scenario in which a system is to be deployed over a fixed horizon but with a limit on the number of times that the health state can be scanned and the system can be reset. Each health state is assigned a cost according to the performance of the system while in that state. Dynamic Programming is then used to find an optimal admissible policy (one that obeys the usage limitation constraints) which achieves the lowest expected aggregate cost. Finally, we examine some properties of the solution.

In this paper we profile a particular tradeoff between power budget and video quality that emerges in the transmission of multimedia packets over a wireless channel. These packets are due to arrive to a receiver at a particular time, so we consider a finite horizon problem over which multimedia data are transmitted. Due to the lossy nature of the wireless channel, however, not every packet can be successfully sent across the channel. Hence, each packet that is lost leads to distortion in the video that is experienced by the receiver. We suppose that there are M packets that must arrive at the receiver within N time steps, but that power limitations constrain the number of transmissions. At each time step, we may make a measurement of the wireless channel and decide whether or not to transmit a packet over the channel at that time. First we will suppose the times at which the channel state is sampled are spaced far enough apart so that the samples are i.i.d. Then we will continue by supposing that the channel state follows a Markov chain.

This paper presents a game-theoretic and learning approach to security risk management based on a model that captures the diffusion of risk in an organization with multiple technical and business processes. Of particular interest is the way the interdependencies between processes affect the evolution of the organization's risk profile as time progresses, which is first developed as a probabilistic risk framework and then studied within a discrete Markov model. Using zero-sum dynamic Markov games, we analyze the interaction between a malicious adversary whose actions increases the risk level of the organization and a defender agent, e.g. security and risk management division of the organization, which aims to mitigate risks. We derive min-max (saddle point) solutions of this game to obtain the optimal risk management strategies for the organization to achieve a certain level of performance. This methodology also applies to worst-case scenario analysis where the adversary can be interpreted as a nature player in the game. In practice, the parameters of the Markov game may not be known due to the costly nature of collecting and processing information about the adversary as well an organization with many components itself. We apply ideas from Q-learning to analyze the behavior of the agents when little information is known about the environment in which the attacker and defender interact. The framework developed and results obtained are illustrated with a small example scenario and numerical analysis.

We present a model for keeping track of vulnerabilities in a networked computing system and study the tradeoff between risk mitigation and keeping disruption at an acceptable level. The tradeoff is such that one can either choose to perform maintenance of the computing system very frequently and experience low risk, or disrupt the system with less frequency, but bear more risk. Formally, we suppose there are n types of vulnerabilities, where each type is jointly characterized by (i) maliciousness, as measured by risk per time slot due to its presence and (ii) probability of occurrence. At each time step, at most one new vulnerability appears in the system, a property that follows if we take the discretized time step size to be small compared to the rate of arrivals for vulnerabilities. We consider a finite-horizon framework of duration N in which the number of times the network may be patched is M <; N. This limitation captures the fact that in many engineering systems we would like to limit the number of times processes are interrupted for maintenance. Indeed, service providers may wish to promise clients that service will be disrupted no more than M times so that a certain level of operational continuity can be guaranteed. We develop an optimal policy for mitigating the risk due to exposure from vulnerabilities while obeying the patching constraint.