Arrow Research search

Author name cluster

Andrei Z. Broder

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
2 author rows

Possible papers

32

TIST Journal 2011 Journal Article

Web Page Summarization for Just-in-Time Contextual Advertising

  • Aris Anagnostopoulos
  • Andrei Z. Broder
  • Evgeniy Gabrilovich
  • Vanja Josifovski
  • Lance Riedel

Contextual advertising is a type of Web advertising, which, given the URL of a Web page, aims to embed into the page the most relevant textual ads available. For static pages that are displayed repeatedly, the matching of ads can be based on prior analysis of their entire content; however, often ads need to be matched to new or dynamically created pages that cannot be processed ahead of time. Analyzing the entire content of such pages on-the-fly entails prohibitive communication and latency costs. To solve the three-horned dilemma of either low relevance or high latency or high load, we propose to use text summarization techniques paired with external knowledge (exogenous to the page) to craft short page summaries in real time. Empirical evaluation proves that matching ads on the basis of such summaries does not sacrifice relevance, and is competitive with matching based on the entire page content. Specifically, we found that analyzing a carefully selected 6% fraction of the page text can sacrifice only 1%--3% in ad relevance. Furthermore, our summaries are fully compatible with the standard JavaScript mechanisms used for ad placement: they can be produced at ad-display time by simple additions to the usual script, and they only add 500--600 bytes to the usual request. We also compared our summarization approach, which is based on structural properties of the HTML content of the page, with a more principled one based on one of the standard text summarization tools (MEAD), and found their performance to be comparable.

Details DOI

FOCS Conference 1996 Conference Paper

A General Approach to Dynamic Packet Routing with Bounded Buffers (extended abstract)

  • Andrei Z. Broder
  • Alan M. Frieze
  • Eli Upfal

We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static routing. We show that certain high probability and worst case bounds on the quasistatic (finite past) performance of a routing algorithm imply bounds on the performance of the dynamic version of that algorithm. Our technique is particularly useful in analyzing routing on networks with bounded buffers where complicated dependencies make standard queuing techniques inapplicable. We present several applications of our approach. In all cases we start from a known static algorithm, and modify it to fit our framework. In particular we give the first dynamic algorithm for routing on a butterfly with bounded buffers. Both the injection rate for which the algorithm is stable, and the expected time a packet spends in the system are optimal up to constant factors. Our approach is also applicable to the recently introduced adversarial input model.

Details

FOCS Conference 1992 Conference Paper

On-line Load Balancing (Extended Abstract)

  • Yossi Azar
  • Andrei Z. Broder
  • Anna R. Karlin

The setup for the authors' problem consists of n servers that must complete a set of tasks. Each task can be handled only by a subset of the servers, requires a different level of service, and once assigned can not be re-assigned. They make the natural assumption that the level of service is known at arrival time, but that the duration of service is not. The on-line load balancing problem is to assign each task to an appropriate server in such a way that the maximum load on the servers is minimized. The authors derive matching upper and lower bounds for the competitive ratio of the on-line greedy algorithm for this problem, namely /sup (3n)2/3///sub 2/(1+o(1)), and derive a lower bound, Omega ( square root n), for any other deterministic or randomized on-line algorithm. >

Details

FOCS Conference 1989 Conference Paper

Generating Random Spanning Trees

  • Andrei Z. Broder

The author describes a probabilistic algorithm that, given a connected, undirected graph G with n vertices, produces a spanning tree of G chosen uniformly at random among the spanning trees of G. The expected running time is O(n log n) per generated tree for almost all graphs, and O(n/sup 3/) for the worst graphs. Previously known deterministic algorithms are much more complicated and require O(n/sup 3/) time per generated tree. A Markov chain is called rapidly mixing if it gets close to the limit distribution in time polynomial in the log of the number of states. Starting from the analysis of the above algorithm, it is shown that the Markov chain on the space of all spanning trees of a given graph where the basic step is an edge swap is rapidly mixing. >

Details

FOCS Conference 1988 Conference Paper

Bounds on the Cover Time (Preliminary Version)

  • Andrei Z. Broder
  • Anna R. Karlin

A particle that moves on a connected unidirected graph G with n vertices is considered. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. The cover time is the first time when the particle has visited all the vertices in the graph, starting from a given vertex. Upper and lower bounds are presented that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the above random walk. An interesting consequence is that regular expander graphs have expected cover time theta (n log n). >

Details

FOCS Conference 1987 Conference Paper

On the Second Eigenvalue of Random Regular Graphs (Preliminary Version)

  • Andrei Z. Broder
  • Eli Shamir 0001

Expanders have many applications in Computer Science. It is known that random d-regular graphs are very efficient expanders, almost surely. However, checking whether a particular graph is a good expander is co-NP-complete. We show that the second eigenvalue of d-regular graphs, λ2, is concentrated in an interval of width O(√d) around its mean, and that its mean is O(d3/4). The result holds under various models for random d-regular graphs. As a consequence a random d-regular graph on n vertices, is, with high probability a certifiable efficient expander for n sufficiently large. The bound on the width of the interval is derived from martingale theory and the bound on E(λ2) is obtained by exploring the properties of random walks in random graphs.

Details

FOCS Conference 1984 Conference Paper

Flipping coins in many pockets (Byzantine agreement on uniformly random values)

  • Andrei Z. Broder
  • Danny Dolev

It was recently shown by Michael Rabin that a sequence of random 0-1 values, prepared and distributed by a trusted "dealer, " can be used to achieve Byzantine agreement in constant expected time in a network of processors. A natural question is whether it is possible to generate these values uniformly at random within the network. In this paper we present a cryptography based protocol for agreernent on a 0-1 randona value, if less than half of the processors are faulty. In fact the protocol allows uniform sampling from any finite set, and thus solves the problem of choosing a network leader uniformly at random. The protocol is usable both when all the communication is via "broadcast, " in which case it needs three rounds of information exchange, and when each pair of processors communicate on a private line, in which case it needs 3t + 3 rounds, where t is the number of faulty proccssors. The protocol remains valid even if passive eavesdropping is allowed. On the other hand we show that no (probabilistic) protocol can achieve agreement on a fair coin in fewer phases then necessary for Byzantine agreement, and hence the "pre-dealt" nature of the random sequence required for Rabin's algorithm is crucial.

Details