We propose a highly efficient and effective algorithm to estimate metrics on very large graphs that are based on the neighborhood function: examples of such metrics are the (effective) diameter and (effective) radius or the average distance. In order to efficiently provide good approximations to the size of the neighborhood set of any node, we refer to the MinHash Signatures approach to derive compressed representations of large sparse datasets but preserving similarity. The technique introduced here, named MinHash Signature Estimation (MHSE), exploits the similarity between signatures to estimate the size of the neighborhood function. We show that MHSE is as effective as HyperANF, which is considered the state of art approach for the estimation of the effective diameter of a very large graph. Indeed, performing both parametric (t-test) and non-parametric (Wilcoxon) statistical tests on residuals for average distance, effective diameter and number of connected pairs, the p-values show that MHSE tends to be more statistically significant than HyperANF. On the other hand, we show that MHSE is a very simple and easily distributable algorithm. In addition, by the property of the signatures to preserve similarity between neighborhoods of nodes, the algorithm can be suitably applied to allow to search and estimate the overlapping size of the most similar neighborhood at different distances.

We present the results of our exploratory analysis on the relationship that exists between relevance and time. We observe how the amount of documents published in a given interval of time is related to the probability of relevance, and, using the time series analysis, we show the existence of a correlation between time and relevance. As an initial application of this analysis, we study query expansion exploiting the detection of publication time peaks over the Blog06 collection. We finally propose an effective approach for the query expansion in the blog search domain. Our approach is based on the documents publication trend being so completely independent of any external resource.

We investigate the effectiveness of both the standard evaluation measures and the opinion component for topical opinion retrieval. We analyze how relevance is affected by opinions by perturbing relevance ranking by the outcomes of opinion-only classifiers built by Monte Carlo sampling. Topical opinion rankings are obtained by either re-ranking or filtering the documents of a first-pass retrieval of topic relevance.

In this paper we present NetPrIDE, an integrated development environment for designing, implementing and visualizing computer network protocols, which has primarily been used for teaching computer networks. NetPrIDE makes use of an abstract and formal notation to clearly and firmly specify a protocol: once the protocol has been specified and the network topology has been fixed, the implementation and the visualization of the protocol is performed in a completely automated way.

Abstract We give complete characterizations for the classes of graphs with uniform cost links that admit optimum all shortest paths 1‐SLIRS (strict linear interval routing schemes) and 1‐LIRS (linear interval routing schemes). The characterization of all the interval routing schemes with uniform cost links that represent only a single shortest path is known to be NP‐complete. For any integer k > 0, we also show that the class of graphs with dynamic cost links that admit optimum all shortest paths k‐IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum single shortest path k‐IRS (SIRS, LIRS, SLIRS) and also equivalent to the class of graphs with dynamic cost links that admit single paths up to any constant stretch factor k‐IRS (SIRS, LIRS, SLIRS). © 2001 John Wiley & Sons, Inc.

The typical online bin-packing problem requires the fitting of a sequence of rationals in (0,1] into a minimum number of bins of unit capacity, by packing the ith input element without any knowledge of the sizes or the number of input elements that follow. Moreover, unlike typical online problems, this one issue does not admit any data reorganization, i.e., no element can be moved from one bin to another. In this paper, first of all, the "Relaxed" online bin-packing model will be formalized; this model allows a constant number of elements to move from one bin to another, as a consequence of the arrival of a new input element. Then, in the context of this new model, two online algorithms will be described. The first presents linear time and space complexities with a 1.5 approximation ratio and moves, at most once, only "small" elements; the second, instead, is an O(n log n) time and linear space algorithm with a 1.33. . . approximation ratio and moves each element a constant number of times. In the worst case, as a result of the arrival of a new input element, the first algorithm moves no more than three elements, while the second moves as many as seven elements. Please note that the number of movements performed is explicitly considered in the complexity analysis. Both algorithms are below the theoretical 1.536. . . lower bound, effective for the online bin-packing algorithms without the movement of elements. Moreover, our algorithms are "more online" than any other linear space online bin-packing algorithm because, unlike the algorithms already known, they allow the return of a (possibly relevant) fraction of bins before the work is carried out.

An extension of the disjoint set union problem is considered, where the extra primitive backtrack $(i)$ can undo the last i unions not yet undone. Let n be the total number of elements in all the sets. A data structure is presented that supports each union and find in $O({{\log n} / {\log \log n}})$ worst-case time and each backtrack$(i)$ in $O(1)$ worst-case time, irrespective of i. The total space required by the data structure is $O(n)$. A byproduct of this construction is a partially persistent data structure for the standard set union problem, capable of supporting union, find, and find-in-the-past operations, each in $O({{\log n} / {\log \log n}})$ worst-case time. All these upper bounds are tight for the class of separable-pointer algorithms as well as in the cell probe model of computation.

A problem of deadlock avoidance in store-and-forward networks with at least two buffers per node is considered for fixed as well as dynamic routing. For both cases polynomial time, centralized deadlock avoidance algorithms are proposed and shown to be optimal in a sense of possible buffer utilization. When the number of buffers is equal to one for each node the problem is known to be NP-complete, thus, unlikely to admit a polynomial-time algorithm. The presented results may be also interesting for other applications, some massively parallel computer systems being one of the examples.>

This paper deals with the problem of store-and-forward deadlock prevention in store-and-forward networks. The presented solution uses time stamping of all messages in the network, and a nonpreemptable message exchange mechanism. By combining these ideas, a new distributed flow control procedure is derived which guarantees that all messages are delivered to their own destinations, thus avoiding both deadlock and livelock without any message loss. It is shown that some properties of this procedure depend on the policy of the allocation of exchange buffers to nodes. On the one hand, an optimal allocation strategy is presented which results in a maximally optimal deadlock prevention procedure. The procedure is network sizeand topology-independent and allows unrestricted packet routing. On the other hand, the allocation of one exchange buffer per node is discussed, which, even if not optimal, makes the derived deadlock prevention procedure completely independent of network reconfigurations. The last feature is extremely important from the practical point of view and, therefore, such a solution is strongly recommended. When compared to store-and-forward deadlock prevention procedures described so far, which lack some or all of these desirable properties, the procedure presented here behaves favorably. However, it imposes other drawbacks, i.e., the possibility of extra hops as a result of exchange operations. It is argued that this drawback appears rarely in practice, and some strategies which aim at a reduction of it are proposed.

This correspondence is concerned with the prevention of four types of deadlock in store-and-forward networks, i.e., progeny, copy-release, reassembly, and resequence deadlocks. The approach presented makes use of time stamping of all messages and generalizes the method of store-and-forward deadlock prevention.

A flow control procedure for an acyclic store-and-forward network is introduced which uses only information local to each node and is deadlock-resistant (i.e., detects and recovers deadlock at a negligible cost). The procedure requires less than3n/2buffers (the exact value depending on the network topology), wherenis the number of nodes in the network. It is shown that this number is lower bound for distributed deadlock-resistant procedures. From a practical point of view, this means that a single buffer class is sufficient, provided that the exchange mechanism for input buffers is realized as a synchronized procedure between any two contiguous nodes (rather than as a purely local procedure). Some extension to more general networks are then proposed.