Graphs are an increasingly important data source, with such important graphs as the Internet and the Web. Other familiar graphs include CAD circuits, phone records, gene sequences, city streets, social networks and academic citations. Any kind of relationship, such as actors appearing in movies, can be represented as a graph. This work presents a data mining tool, called ANF, that can quickly answer a number of interesting questions on graph-represented data, such as the following. How robust is the Internet to failures? What are the most influential database papers? Are there gender differences in movie appearance patterns? At its core, ANF is based on a fast and memory-efficient approach for approximating the complete neighbourhood function for a graph. For the Internet graph (268K nodes), ANF's highly-accurate approximation is more than 700 times faster than the exact computation. This reduces the running time from nearly a day to a matter of a minute or two, allowing users to perform ad hoc drill-down tasks and to repeatedly answer questions about changing data sources. To enable this drill-down, ANF employs new techniques for approximating neighbourhood-type functions for graphs with distinguished nodes and/or edges. When compared to the best existing approximation, ANF's approach is both faster and more accurate, given the same resources. Additionally, unlike previous approaches, ANF scales gracefully to handle disk resident graphs. Finally, we present some of our results from mining large graphs using ANF.

In this paper, we develop a conceptual visual model for the Internet inter-domain topology. Recently, power-laws were used to describe the topology concisely. Despite their success, the power-laws do not help us visualize the topology, ie, draw the topology on paper by hand. In this paper, we deal with the following questions: can we identify a hierarchy in the Internet; how can I represent the network in an abstract graphical way? The focus of this paper is threefold. First, we characterize nodes using three metrics of topological "importance"', which we later use to identify a sense of hierarchy. Second, we identify some new topological properties. We then find that the Internet has a highly connected core and identify layers of nodes in decreasing importance surrounding the core. Finally, we show that our observations suggest an intuitive model. The topology can be seen as a jellyfish, where the core is in the middle of the cap, and one-degree nodes form its legs.

Recent studies have shown that Internet graphs and other network systems follow power-laws. Are these laws obeyed by the artificial network topologies used in network simulations? Does it matter? In this paper we show that current topology generators do not obey all of the power-laws, and we present two new topology generators that do. We also re-evaluate a multicast study to show the impact of using power-law topologies.

Data mining in large data sets often requires a sampling or summarization step to form an in-core representation of the data that can be processed more efficiently. Uniform random sampling is frequently used in practice and also frequently criticized because it will miss small clusters. Many natural phenomena are known to follow Zipf's distribution and the inability of uniform sampling to find small clusters is of practical concern. Density Biased Sampling is proposed to probabilistically under-sample dense regions and over-sample light regions. A weighted sample is used to preserve the densities of the original data. Density biased sampling naturally includes uniform sampling as a special case. A memory efficient algorithm is proposed that approximates density biased sampling using only a single scan of the data. We empirically evaluate density biased sampling using synthetic data sets that exhibit varying cluster size distributions finding up to a factor of six improvement over uniform sampling.

No abstract available.

No abstract available.

The Distributed Operation Dansform (dOPT), pr~ posed by Efi and Gibbs, is used to dfie concurrently updatable shared objects.Eh and Gibbs give the OP eration tr~orrus that d&e a simple shared text editor supporting single chmacter insertions and deletions on a hear btim.We report here on the construction of operation transforms for a more sophisticated group nwe appficatiou a shared spreadsheet.We identify a set of abstract operations that &aracterize the operations on a spreadsheet.Using Cormack's Cdtius for Concurrent Update, which extends and corrects dOPT, m'egive the tr~forms on these operations necessary to d~e a shared spreadsheet.~re use the transforms to btid a shared version of SC, the Unix spreadsheet due to Goshg.

Test collections with a million or more documents are needed for the evaluation of modern information retrieval systems.Yet their construction requires a great deal of effort.Judgements must be rendered as to whether or not documents are relevant to each of a set of queries.Exhaustive judging, in which every document is examined and a judgement rendered, is infeasible for collections of this size.Current practice is represented by the "pooling method", as used in the TREC conference series, in which only the first k documents from each of a number of sources are judged.We propose two methods, Intemctive Searching and Judging and Moveto-front Pooling, that yield effective test collections while requiring many fewer judgements.Interactive Searching and Judging selects documents to be judged using an interactive search system, and may be used by a small research team to develop an effective test collection using minimal resources.Move-to-Front Pooling directly improves on the standard pooling method by using a variable number of documents from each source depending on its retrieval performance.Move-to-Front Pooling would be an appropriate replacement for the standard pooling method in future collection development efforts involving many independent groups.