Graph embedding, which maps graph nodes to lowdimensional vectors, is a widely used technique for graph representation learning. However, most existing graph embedding models suffer from high memory consumption, limiting their scalability to large graphs. Heterogeneous memory systems that combine DRAM and Persistent Memory (PM) offer new opportunities for scaling up memory capacity. Despite this advantage, the performance gap (on the order of 5x) between DRAM and PM is magnified (by 3.3-4.2x) under non-uniform memory access (NUMA) architecture. Additionally, the inherent sparsity of graphs induces numerous random accesses in the fundamental Sparse Matrix and Dense Matrix Multiplication (SpMM) operations of graph embedding, hindering high-performance heterogeneous memory processing. To address these challenges, this paper presents OMeGa that focuses on Optimizing heterogeneous Memory processing for large-scale Graph embedding. OMeGa leverages an entropy-aware thread allocation, simultaneously achieving workload balancing and tail latency reduction across threads. It also incorporates a workload feature-aware prefetcher to alleviate random accesses during streaming heterogeneous processing. In addition, OMeGa devises a NUMA-aware data placement, aiming to minimize the adverse impact of NUMA on heterogeneous memory. The experiments conducted on billion-scale graphs demonstrate that OMeGa exhibits an average acceleration of 32.03x with strong scalability. This pioneering capability enables the efficient generation of large-scale graph embeddings, free from the memory size constraints and performance disparities typically encountered in heterogeneous memory systems.

Our extensive experiments reveal that existing key-value stores (KVSs) achieve high performance at the expense of a huge memory footprint that is often impractical or unacceptable. Even with the emerging ultra-fast byte-addressable persistent memory (PM), KVSs fall far short of delivering the high performance promised by PM's superior I/O bandwidth. To find the root causes and bridge the huge performance/memory-footprint gap, we revisit the architectural features of two representative indexing mechanisms (single-stage and multi-stage) and propose a three-stage KVS called FluidKV. FluidKV effectively consolidates these indexes by fast and seamlessly running incoming key-value request stream from the write-concurrent frontend stage to the memory-efficient backend stage across an intermediate stage. FluidKV also designs important enabling techniques, such as thread-exclusive logging, PM-friendly KV-block structures, and dual-grained indexes, to fully utilize both parallel-processing and high-bandwidth capabilities of ultra-fast storage hardware while reducing the overhead. We implemented a FluidKV prototype and evaluated it under a variety of workloads. The results show that FluidKV outperforms the state-of-the-art PM-aware KVSs, including ListDB and FlatStore with different indexes, by up to 9× and 3.9× in write and read throughput respectively, while cutting up to 90% of the DRAM footprint.

Graph embedding is becoming widely adopted as an efficient way to learn graph representations required to solve graph analytics problems. However, most existing graph embedding methods, owing to computation-efficiency challenges for large-scale graphs, generally employ a one-size-fits-all strategy to extract information, resulting in a large amount of redundant or inaccurate representations. In this work, we propose HuGE, an efficient and scalable graph embedding method enabled by an entropy-driven mechanism. Specifically, HuGE leverages hybrid-property heuristic random walk to capture node features, which considers both node degree and the number of common neighbors in each walking step. More importantly, to guarantee information effectiveness of sampling, HuGE adopts two heuristic methods to decide the random walk length and the number of walks per node, respectively. Extensive experiments on real-world graphs demonstrate that HuGE achieves both efficiency and performance advantages over recent popular graph embedding approaches. For link prediction and multi-label classification, our approach not only offers >10% average gains, but also exhibits 22×-126× speedup compared with existing sampling-based methods.

Reservoir sampling is widely employed to characterize connectivity of large graph streams by producing edge samples. However, existing reservoir-based sampling methods mainly characterize large graph streams by a measure of counting triangles but perform poorly in accuracy when used to analyze the topological characteristics reflected by node degrees because they produce disconnected edge samples, making them ineffective in many applications that require both types of connectivity estimation simultaneously in real time. This paper proposes a new method, called triangle-induced reservoir sampling, or T-Sample, to produce connected edge samples. While every edge in a graph stream is still processed only once by T-Sample, a dual sampling mechanism performing both uniform sampling and non-uniform sampling is carefully designed with a base reservoir and an incremental reservoir. Specifically, the uniform sampling can be used to count triangles by employing the existing algorithms while the non-uniform sampling ensures that the edge samples are connected. Experimental results driven by real datasets show that T-Sample can obtain much more accurate estimations on the distributions of node degrees than the existing reservoir-based sampling methods.

Data reduction has become increasingly important in storage systems due to the explosive growth of digital data in the world that has ushered in the big data era. In this paper, we present DARE, a Deduplication-Aware Resemblance detection and Elimination scheme for compressing backup datasets that effectively combines data deduplication and delta compression to achieve high data reduction efficiency at low overhead. The main idea behind DARE is to employ a scheme, call Duplicate-Adjacency based Resemblance Detection (DupAdj), by considering any two data chunks to be similar (i.e., candidates for delta compression) if their respective adjacent data chunks are found to be duplicate in a deduplication system, and then further enhance the resemblance detection efficiency by an improved super-feature approach. Our experimental results based on real-world and synthetic backup datasets show that DARE achieves an additional data reduction by a factor of more than 2 (2X) on top of deduplication with very low overhead while nearly doubling the data restore performance of deduplication-only systems by supplementing delta compression to deduplication.