How can we efficiently index extensive high-dimensional vector data increasing over time, enabling quick and accurate proximity searches within designated time windows? A time-restricted \( k \) -Nearest Neighbor (T \( k \) NN) query aims to identify the \( k \) -nearest vectors to a query vector within a specified time window. While high-dimensional and time-accumulating data are ubiquitous and managing such data efficiently is becoming increasingly significant, T \( k \) NN search within this context has not received much attention so far. In this article, we propose Multi-Level Block Indexing (MBI), a tailored indexing method for efficient approximate T \( k \) NN search. MBI employs an incremental hierarchical index structure that divides the data into multiple blocks based on timestamps. This structure ensures efficient query processing, irrespective of the length of the query time window, and facilitates the addition of new data over time. Furthermore, we extend T \( k \) NN beyond timestamps to the \( m \) -A \( k \) NN problem, incorporating \( m \) additional attributes—such as age, height, and weight in medical data or citation counts in academic papers—allowing queries to integrate multiple numerical constraints. Experimental results highlight MBI’s superiority over conventional methods, achieving query processing speeds up to 10.88 times faster and offering logarithmic scaling in data insertion time as the data volume grows. Additionally, in \( m \) -A \( k \) NN queries, MBI maintains stable indexing performance and achieves up to 1.99 times faster query performance, demonstrating its effectiveness in large-scale, multi-attribute \( k \) NN search.

How can we efficiently find connected components with Union-Find in a distributed system? Union-Find is the most efficient sequential algorithm for finding connected components with low memory usage and high speed. Several studies have adapted Union-Find to distributed memory systems to process large graphs quickly; however, they all suffer from load balancing problems. We notice that the leading cause of the load balancing problems is the nature of Union-Find, which gathers more and more edges to a small number of vertices as it proceeds. In this paper, we propose BTS, a new fast and scalable distributed Union-Find algorithm for finding connected components in large graphs. BTS resolves the load balancing problems by proposing Balanced Union-Find, which allocates vertices to each processor and makes edges link to vertices in the same processor as much as possible. We further optimize BTS with edge refinement to minimize network traffic and memory usage. Experimental results show that BTS efficiently resolves the load balancing problems, processing 16–1024 times larger graphs with 3.1-261.9 times faster speeds than existing algorithms.

k-nearest neighbor graphs, shortly k-NN graphs, are widely used in many data mining applications like recommendation, information retrieval, and similarity search. Approximate k-NN graph construction has been getting a lot of attention, and most researches focus on developing algorithms that operate efficiently and quickly on a single machine. A few pioneering studies propose distributed algorithms to increase the size of data that can be processed to billions. However, we notice that the distributed algorithms don't perform well enough due to the problems of graph fragmentation and massive data exchange. In this paper, we propose MRDF (Multiway Random Division Forest), a scalable distributed algorithm that constructs highly accurate k-NN graph from numerous high-dimensional vectors quickly. MRDF resolves the problems that the existing distributed algorithms suffer from, through coarse-grained partitioning based on tree path annotation. Experimental results on real-world datasets show that MRDF outperforms the state-of-the-art distributed algorithms with up to 7.6 times faster speed and up to 56%p better accuracy than the second best results.

How can we find patterns from an enormous graph with billions of vertices and edges? The subgraph enumeration, which is to find patterns from a graph, is an important task for graph data analysis with many applications, including analyzing the social network evolution, measuring the significance of motifs in biological networks, observing the dynamics of Internet, and so on. Especially, the triangle enumeration, a special case of the subgraph enumeration, where the pattern is a triangle, has many applications such as identifying suspicious users in social networks, detecting web spams, and finding communities. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this article, we propose scalable methods for enumerating trillion subgraphs on distributed systems. We first propose PTE ( Pre-partitioned Triangle Enumeration ), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read. We also propose PSE ( Pre-partitioned Subgraph Enumeration ), a generalized version of PTE for enumerating subgraphs that match an arbitrary query graph. Experimental results show that PTE provides 79 times faster performance than recent distributed algorithms on real-world graphs, and succeeds in enumerating more than 3 trillion triangles on the ClueWeb12 graph with 6.3 billion vertices and 72 billion edges. Furthermore, PSE successfully enumerates 265 trillion clique subgraphs with 4 vertices from a subdomain hyperlink network, showing 47 times faster performance than the state of the art distributed subgraph enumeration algorithm.

How can we find all connected components in an enormous graph with billions of nodes and edges?Finding connected components is a fundamental operation for various graph computation tasks such as pattern recognition, reachability, graph compression, etc. Many algorithms have been proposed for decades, but most of them are not scalable enough to process recent web scale graphs. Recently, a MapReduce algorithm was proposed to handle such large graphs. However, the algorithm repeatedly reads and writes numerous intermediate data that cause network overload and prolong the running time. In this paper, we propose PACC (Partition-Aware Connected Components), a new distributed algorithm based on graph partitioning for load-balancing and edge-filtering. Experimental results show that PACC significantly reduces the intermediate data, and provides up to 10 times faster performance than the current state-of-the-art MapReduce algorithm on real world graphs.

How can we enumerate triangles from an enormous graph with billions of vertices and edges? Triangle enumeration is an important task for graph data analysis with many applications including identifying suspicious users in social networks, detecting web spams, finding communities, etc. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this paper, we propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read.

We describe an optimal randomized MapReduce algorithm for the problem of triangle enumeration that requires O(E3/2/(M√m) rounds, where m denotes the expected memory size of a reducer and M the total available space. This generalizes the well-known vertex partitioning approach proposed in (Suri and Vassilvitskii, 2011) to multiple rounds, significantly increasing the size of the graphs that can be handled on a given system. We also give new theoretical (high probability) bounds on the work needed in each reducer, addressing the "curse of the last reducer". Indeed, our work is the first to give guarantees on the maximum load of each reducer for an arbitrary input graph. Our experimental evaluation shows the scalability of our approach, that it is competitive with existing methods improving the performance by a factor up to 2X, and that it can significantly increase the size of datasets that can be processed.

Triangle counting problem is one of the fundamental problem in various domains. The problem can be utilized for computation of clustering coefficient, transitivity, trianglular connectivity, trusses, etc. The problem have been extensively studied in internal memory but the algorithms are not scalable for enormous graphs. In recent years, the MapReduce has emerged as a de facto standard framework for processing large data through parallel computing. A MapReduce algorithm was proposed for the problem based on graph partitioning. However, the algorithm redundantly generates a large number of intermediate data that cause network overload and prolong the processing time. In this paper, we propose a new algorithm based on graph partitioning with a novel idea of triangle classification to count the number of triangles in a graph. The algorithm substantially reduces the duplication by classifying triangles into three types and processing each triangle differently according to its type. In the experiments, we compare the proposed algorithm with recent existing algorithms using both synthetic datasets and real-world datasets that are composed of millions of nodes and billions of edges. The proposed algorithm outperforms other algorithms in most cases. Especially, for a twitter dataset, the proposed algorithm is more than twice as fast as existing MapReduce algorithms. Moreover, the performance gap increases as the graph becomes larger and denser.