Betweenness centrality is one of the most well-known measures of the importance of nodes in a social-network graph. In this paper we describe the first known external-memory and cache-oblivious algorithms for computing betweenness centrality. We present four different external-memory algorithms exhibiting various tradeoffs with respect to performance. Two of the algorithms are cache-oblivious. We describe general algorithms for networks with weighted and unweighted edges and a specialized algorithm for networks with small diameters, as is common in social networks exhibiting the “small worlds” phenomenon.

Range reporting on categorical (or colored) data is a well-studied generalization of the classical range reporting problem in which each of the N input points has an associated color (category). A query then asks to report the set of colors of the points in a given rectangular query range, which may be far smaller than the set of all points in the query range. We study two-dimensional categorical range reporting in both the word-RAM and I/O-model. For the I/O-model, we present two alternative data structures for three-sided queries. The first answers queries in optimal O(lgB N + K/B) I/Os using O(N lg* N) space, where K is the number of distinct colors in the output, B is the disk block size, and lg* N is the iterated logarithm of N. Our second data structure uses linear space and answers queries in O(lgB N + lg(h) N + K/B) I/Os for any constant integer h ≥ 1. Here lg(1) N = lg N and lg(h) N = lg(lg(h − 1) N) when h > 1. Both solutions use only comparisons on the coordinates. We also show that the lgB N terms in the query costs can be reduced to optimal lg lgB U when the input points lie on a U × U grid and we allow word-level manipulations of the coordinates. We further reduce the query time to just O(1) if the points are given on an N × N grid. Both solutions also lead to improved data structures for four-sided queries. For the word-RAM, we obtain optimal data structures for three-sided range reporting, as well as improved upper bounds for four-sided range reporting. Finally, we show a tight lower bound on one-dimensional categorical range counting using an elegant reduction from (standard) two-dimensional range counting.

We revisit I/O-efficient solutions to a number of fundamental problems on planar graphs: single-source shortest paths, topological sorting, and computing strongly connected components. Existing I/O-efficient solutions to these problems pay for I/O efficiency using excessive computation time in internal memory, thereby completely negating the performance gain achieved by minimizing the number of disk accesses. In this paper, we show how to make these algorithms simultaneously efficient in internal and external memory so they achieve I/O complexity O(sort(N)) and take O(N log N) time in internal memory, where sort(N) is the number of I/Os needed to sort N items in external memory. The key, and the main technical contribution of this paper, is a multiway version of Miller's simple cycle separator theorem. We show how to compute these separators in linear time in internal memory, and using O(sort(N)) I/Os and O(N log N) (internal-memory computation) time in external memory.

We consider the problem of automatically cleaning massive sonar data point clouds, that is, the problem of automat-ically removing noisy points that for example appear as a result of scans of (shoals of) fish, multiple reflections, scan-ner self-reflections, refraction in gas bubbles, and so on. We describe a new algorithm that avoids the problems of previous local-neighbourhood based algorithms. Our algo-rithm is theoretically I/O-efficient, that is, it is capable of efficiently processing massive sonar point clouds that do not fit in internal memory but must reside on disk. The algo-rithm is also relatively simple and thus practically efficient, partly due to the development of a new simple algorithm for computing the connected components of a graph embedded in the plane. A version of our cleaning algorithm has already been incorporated in a commercial product. Categories and Subject Descriptors: F.2.2 [Analysis of algorithms and problem complexity]: Nonnumerical algo-rithms and problems—Geometrical problems and computa-tions

Two-dimensional R-trees are a class of spatial index structures in which objects are arranged to enable fast window queries: report all objects that intersect a given query window.One of the most successful methods of arranging the objects in the index structure is based on sorting the objects according to the positions of their centres along a two-dimensional Hilbert spacefilling curve.Alternatively one may use the coordinates of the objects' bounding boxes to represent each object by a four-dimensional point, and sort these points along a four-dimensional Hilbert-type curve.In experiments by Kamel and Faloutsos and by Arge et al. the first solution consistently outperformed the latter when applied to point data, while the latter solution clearly outperformed the first on certain artificial rectangle data.These authors did not specify which four-dimensional Hilbert-type curve was used; many exist.In this paper we show that the results of the previous papers can be explained by the choice of the fourdimensional Hilbert-type curve that was used and by the way it was rotated in four-dimensional space.By selecting a curve that has certain properties and choosing the right rotation one can combine the strengths of the two-dimensional and the four-dimensional approach into one, while avoiding their apparent weaknesses.The effectiveness of our approach is demonstrated with experiments on various data sets.For real data taken from VLSI design, our new curve yields R-trees with query times that are better than those of R-trees that were obtained with previously used curves.