Time-evolving web and social network graphs are modeled as a set of pages/individuals (nodes) and their arcs (links/relationships) that change over time. Due to their popularity, they have become increasingly massive in terms of their number of nodes, arcs, and lifetimes. However, these graphs are extremely sparse throughout their lifetimes. For example, it is estimated that Facebook has over a billion vertices, yet at any point in time, it has far less than 0.001% of all possible relationships. The space required to store these large sparse graphs may not fit in most main memories using underlying representations such as a series of adjacency matrices or adjacency lists. We propose building a compressed data structure that has a compressed binary tree corresponding to each row of each adjacency matrix of the time-evolving graph. We do not explicitly construct the adjacency matrix, and our algorithms take the time-evolving arc list representation as input for its construction. Our compressed structure allows for directed and undirected graphs, faster arc and neighborhood queries, as well as the ability for arcs and frames to be added and removed directly from the compressed structure (streaming operations). We use publicly available network data sets such as Flickr, Yahoo!, and Wikipedia in our experiments and show that our new technique performs as well or better than our benchmarks on all datasets in terms of compression size and other vital metrics.

Matrix multiplication is an essential operation in the field of mathematics and computer science. Many critical computations, such as matrix factorization and graph computations, cast the bulk of their computation in terms of this operation. Thus, it is crucial that this operation is tuned to the data being computed on. In the case of sparse domains, this translates to minimizing the traffic between the CPU and main memory as the amount of work is not necessarily sufficient to amortize the code of the data movement. The amount of memory required to store a nonnegative valued matrix of n rows and m columns requires (n × m) × log2(n) bits. When these dimensions are converted to real world scenarios, for example, a one billion by one billion matrix will require 1000 petabytes of memory, which is impractical. This hinders the ability to perform any operations on the matrix.In this paper, we propose techniques for performing Matrix-Matrix multiplication directly on compressed data stored in two different compression data structures. The structures we consider are the well-known compressed sparse matrix and the Compressed Binary Trees [1]. We test our algorithm on extremely large matrices, in the order of 100s of millions with various levels of sparsity. We show for matrices of order 100 million with 10 million nonzero elements, the space required to store the matrices using the CBT representation is about 6.4MB and requires 13.52s to complete the multiplication using the sequential algorithms provided in this paper.

Time-evolving graphs are structures that encapsulate how a graph changes over time. Thus, we not only have to deal with large graphs consisting of nodes and edges in the billions, but we must also keep track of when these edges activate and deactivate over long lifetimes. In this age of big historical data, we must make use of efficient time-evolving graph compressions, or we will find ourselves quickly out of main memory. These time-evolving graph compressions must not only be space efficient, but must also facilitate fast querying directly on the compressed graph. In this paper, define several novel time-evolving graph problems and develop algorithms to solve them directly on various, massive, synthetic and real-world time-evolving graphs compressed using our technique. Our experiments provide details of the compressed graph sizes, algorithm run times, and other metrics.

Time-evolving graphs represent a set of individuals (nodes) and their edges (relationships) over time. How these graphs are represented in data structures determines what information is easy to obtain from them. Now that we have such massive social networks with dynamic lifetimes, even basic data structures are too large to fit into main memory. Clearly, this poses a problem to areas such as time-evolving graph pattern analysis. Therefore, it is an interesting field of study to design time-evolving graph compressions that can efficiently answer certain queries about the graph at any given point in time.If a single snapshot of a graph at a moment in time can be considered a 2D matrix, then can we visualize these time-evolving graphs as 3D matrices and then use a novel technique to compress the entire graph over time. Our technique is based on our previous work using compressed binary trees. In this work, we adapt our strategy to compress time-evolving graphs, rather than static ones. We manage to maintain our minimal main memory overhead by not requiring an intermediate structure (e.g. adjacency list) to compress. This compression is queryable, meaning that the data can be read without decompression. It is also streaming, meaning that the data can be changed without decompression. This includes adding/removing edges in individual frames. We test our algorithms on public, anonymized, massive, time-evolving graphs such as Flickr, Yahoo!, and Wikipedia. Our empirical evaluation is based on several parameters including time to compress, size of compressed graph, and time to execute queries. Our compression rates are highly competitive, as we achieve the smallest representation of 4.9GB on our largest dataset which only spans three days yet occupies 21.5GB of space.

In this era of social networks, we find ourselves with a collection of massive, changing graphs. Each of these graphs contain a set of nodes (individuals) and a set of edges among the nodes (relationships). How a graph is represented in a data structure determines what information is easy to obtain from it. However, many graphs are so large that even basic data structure representations (e.g. adjacency lists) do not fit in main memory. Therefore, it is an interesting field of study to design compressed data structures that facilitate certain query functions. Since we are dealing with social networks, our structure will also be able to stream edges directly into the compressed graph. We introduce our social network compressed data structure as an indexed array of compressed binary trees. We further minimize memory overhead by directly constructing the graph without any intermediate structure. We also provide fast access methods for edge existence (does an edge exist between two nodes?), neighbor queries (list a node's neighbors), and streaming operations (add/remove nodes/edges). We test our algorithms on public, anonymized, massive graphs such as Friendster, Live-Journal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time to execute queries.

Social networks are constantly changing as new members join, existing members leave, and `followers' or `friends' are formed and disappear. The model that captures this constantly changing graph is the streaming graph model. Given a massive graph data stream wherein the number of nodes is in the order of millions and the number of edges is the tens of millions, we propose a simple algorithm to compress this graph without having read in the entire graph into the main memory. Our algorithm uses the quadtree data structure that is implicitly constructed to produce the compressed graph output. As a result of this implicit construction, our algorithm allows for node and edge additions/deletions that directly modifies the output compressed graph. We further develop algorithms to solve edge queries (is there any between two nodes?) and node queries (for a given node, list all its neighbors) that directly operates on the compressed graph. We have performed extensive empirical evaluations of our algorithms using publicly available, large social networks such as LiveJournal, Pokec, Twitter, and others. Our empirical evaluation is based on several parameters including time to compress, memory required by the compression algorithm, size of compressed graph, and time and memory size required to execute queries. We have also presented extensions to the compression algorithm that we have developed.

Studying the properties of Online Social Networks (OSNs) and other real world graphs have gained importance due to the large amount of information available from them. These large graphs contain data that can be analyzed and effectively used in advertising, security and improving the overall experience of the users of these networks. However, the analysis of these graphs for studying specific properties requires combinatorially explosive number of computations. Compute Unified Device Architecture (CUDA) is a programming model available from Nvidia for solving general-purpose problems using the massively parallel and highly multi-threaded Graphics Processing Units (GPUs). Therefore, using GPUs to solve these types of problems is appropriate. In addition, due to the properties of real-world data, the graphs being considered are sparse and have irregular data dependencies. Hence, using efficient techniques to store the graph data for initial preprocessing and final computation by taking advantage of heterogeneous CPU-GPU systems can address these issues. In this paper, we are interested in studying different properties of these real-world entities that transform into the following graph problems: a) identifying a missing edge, which when added would result in maximum increase in the number of triangles, b) identifying an existing edge whose removal would result in the maximum decrease in the number of triangles, c) identifying an existing edge whose removal would increase the number of connected components in the graph. In this paper, we develop and implement algorithms to solve the above problems using both CPU and GPU. Specifically, given a graph G = (V, E), we provide algorithms for the following: a) find (vi, Vj) ∉ E, such that Δf- Δcis maximized, where Δfand Δcare the number of triangles in Gm= (V, E ∪(vi, Vj)) and G, respectively, b) find a (vi, Vj) ϵ E, such that Δc- Δfis maximized, where Δfand Δcare the number of triangles in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively, c) find a (vi, Vj) ϵ E, such that Φc> Φc, where Φcand Φcare the number of connected components in Gm= (V, E \ (vi, Vj)) and G = (V, E), respectively. We implement the algorithms using a GPU and achieve a 10 × speedup as compared to a sequential implementation. Thereafter, we design a heuristic for finding an edge whose existence would result in the maximum increase in the number of triangles. The heuristic is implemented and the results are reported and compared to those of the regular algorithm on the GPU.

In recent years researchers have become increasingly convinced that the performance of information retrieval systems can be greatly enhanced by the use of key phrases for automatic conceptual document indexing and retrieval. In this article we describe two programs, INDEX and INDEXD, which locate repeated phrases in a document, gather statistical information about them, and rank them according to their value as index phrases. The programs show promise as the basis for a sophisticated conceptual indexing system. The simpler program, INDEX, ranks phrases in such a way that frequently occurring phrases which contain several frequently occurring words are given a high ranking. INDEXD is an extension of INDEX which incorporates a dictionary for stemming, weighting of words and validation of syntax of output phrases. Sample output of both programs is included, and we discuss plans to combine INDEXD with linguistic and artificial intelligence techniques to provide a general conceptual phrase-indexing system that can incorporate expert knowledge about a given application area. © 1990 John Wiley & Sons, Inc.