We consider the problem of duplicate document detection for search evaluation. Given a query and a small number of web results for that query, we show how to detect duplicate web documents with precision ~0.91 and recall ~77. In contrast, Charikar's algorithm, designed for duplicate detection in an indexing pipeline, achieves precision ~0.91 but with a recall of ~0.58. Our improvement in recall while maintaining high precision comes from combining three ideas. First, because we are only concerned with duplicate detection among results for the same query, the number of pairwise comparisons is small. Therefore we can afford to compute multiple pairwise signals for each pair of documents. A model learned with standard machine-learning techniques improves recall to ~0.68 with precision ~0.90. Second, most duplicate detection has focused on text analysis of the HTML contents of a document. In some web pages the HTML is not a good indicator of the final contents of the page. We use extended fetching techniques to fill in frames and execute Java script. Including signals based on our richer fetches further improves the recall to ~0.75 and the precision to ~0.91. Finally, we also explore using signals based on the query. Comparing contextual snippets based on the richer fetches improves the recall to ~0.77. We show that the overall accuracy of this final model approaches that of human judges.

In traditional game theory, players are typically endowed with exogenously given knowledge of the structure of the game--either full omniscient knowledge or partial but fixed information. In real life, however, people are often unaware of the utility of taking a particular action until they perform research into its consequences. In this paper, we model this phenomenon. We imagine a player engaged in a question and- answer session, asking questions both about his or her own preferences and about the state of reality; thus we call this setting "Socratic" game theory. In a Socratic game, players begin with an a priori probability distribution over many possible worlds, with a different utility function for each world. Players can make queries, at some cost, to learn partial information about which of the possible worlds is the actual world, before choosing an action. We consider two query models: (1) an unobservable-query model, in which players learn only the response to their own queries, and (2) an observable-query model, in which players also learn which queries their opponents made.The results in this paper consider cases in which the underlying worlds of a two-player Socratic game are either constant-sum games or strategically zero-sum games, a class that generalizes constant-sum games to include all games in which the sum of payoffs depends linearly on the interaction between the players. When the underlying worlds are constant sum, we give polynomial-time algorithms to find Nash equilibria in both the observable- and unobservable-query models. When the worlds are strategically zero sum, we give efficient algorithms to find Nash equilibria in unobservablequery Socratic games and correlated equilibria in observablequery Socratic games.

An outer bound on the rate region of noise-free information networks is given. This outer bound combines properties of entropy with a strong information inequality derived from the structure of the network. This blend of information theoretic and graph theoretic arguments generates many interesting results. For example, the capacity of directed cycles is characterized. Also, a gap between the sparsity of an undirected graph and its capacity is shown. Extending this result, it is shown that multicommodity flow solutions achieve the capacity in an infinite class of undirected graphs, thereby making progress on a conjecture of Li and Li. This result is in sharp contrast to the situation with directed graphs, where a family of graphs is presented in which the gap between the capacity and the rate achievable using multicommodity flows is linear in the size of the graph.

Using (WDM) technology, an optical network can route multiple signals simultaneously along a single optical fiber by encoding each signal on its own wavelength. If the network contains places where multiple fibers connect together and signals are allowed to be moved from any of the incoming fibers to any of the outgoing fibers, then the network is said to contain cross-connects. More precisely, a $k_1\,\times\,k_2$ WDM cross-connect has k 1 input fibers and k 2 output fibers. Each of the k 1 input fibers supports the same n 1 input wavelengths and each of the k 2 output fibers supports the same n 2 output wavelengths. Since a signal on input wavelength $\lambda$ can be routed from its input fiber to an output fiber such that it arrives on the output fiber using wavelength $\gamma$, where $\lambda \neq \gamma$, the cross-connect must be capable of performing wavelength conversion. Along any fiber in the cross-connect a device called a wavelength interchanger can be inserted to perform wavelength conversion. In other words if the path of a signal from an input fiber to an output fiber passes through a \wins, then the wavelength of the signal can be changed to any wavelength that is not already in use along the fiber leaving the wavelength interchanger. Given the high cost of \wisns, the overall cost of a \CC{k_1}{k_2} is minimized by reducing the number of \wis in the cross-connect. However, a desirable property for a cross-connect C is for C to always be able to provide a route (and wavelength conversion) for any valid demand from any pair of input and output fibers regardless of the routes of other demands currently routed in C. If C has this capability then it is said to be strictly nonblocking. For most of this paper we consider a demand to be a request for a connection from an input fiber to an output fiber such that the connection starts on a specified input wavelength and leaves the ç on a second specified wavelength. Using this demand model, we consider cross-connects for which $k_1$ is not necessarily equal to $k_2$ and the number $n_1$ of supported input wavelengths can differ from the number $n_2$ of supported output wavelengths. Without loss of generality we assume that $k_1 \leq k_2$ and present a family of \snob \CCns{k_1}{k_2}s that use \Opt \wisns. For the case when $k_1 = k_2=k$ and $n_1 = n_2$, we prove that this is optimal. For çs where $n_1$ is not necessarily equal to $n_2$, we show that if there is at most one wavelength interchanger on any path from an input fiber to an output fiber, \Opt \wis are optimal. Finally, we consider a more flexible demand model where $k_1 = k_2$ but the input and output wavelengths are not specified as part of the demand. We show that $2k-1$ \wis are still necessary for any \snob \CC{k}{k}.

We study the route oscillation problem [16, 19] in the Internal Border Gateway Protocol (I-BGP)[18] when route reflection is used. We propose a formal model of I-BGP and use it to show that even deciding whether an I-BGP configuration with route reflection can converge is an NP-Complete problem. We then propose a modification to I-BGP and show that route reflection cannot cause the modified protocol to diverge. Moreover, we show that the modified protocol converges to the same stable routing configuration regardless of the order in which messages are sent or received.

We consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n. The size of this grammar is of theoretical interest as an efficiently computable variant of Kolmogorov complexity. The problem is of practical importance in areas such as data compression and pattern extraction.The smallest grammar is known to be hard to approximate to within a constant factor, and an o(logn/log logn) approximation would require progress on a long-standing algebraic problem [10]. Previously, the best proved approximation ratio was O(n1/2) for the Bisection algorithm [8]. Our main result is an exponential improvement of this ratio; we give an O(log (n/g*)) approximation algorithm, where g* is the size of the smallest grammar.We then consider other computable variants of Kolomogorov complexity. In particular we give an O(log2 n) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. We also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.

Article Strictly non-blocking WDM cross-connects for heterogeneous networks Share on Authors: April Rasala MIT Laboratory for Computer Science, Cambridge, MA MIT Laboratory for Computer Science, Cambridge, MAView Profile , Gordon Wilfong Bell Labs, Lucent Technologies, Murray Hill, NJ Bell Labs, Lucent Technologies, Murray Hill, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 514–523https://doi.org/10.1145/335305.335366Online:01 May 2000Publication History 15citation312DownloadsMetricsTotal Citations15Total Downloads312Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access