wolfram77

See below.

wolfram77

I was trying out the Misra-Gries algorithm for finding heavy hitters in a list of numbers, using vector instructions. But let me fill in some context first. I am trying to minimize the memory needed by Louvain/Leiden algorithms for community detection, and hopefully a bit of performance too. Currently the algorithms use a full-size per-thread hashtables, with each thread using |V| space for storing the associated weights for the hashtable. However, we could instead store a small hashtable, using the Misra-Gries algorithm, in the cache - obviously this might affect the performance (in terms of quality of the returned communities).

It was cool to go through step-by-step and be able to minimize the number of lines of generated machine code (with minimal conditional jumps). When you understand the vector instructions, you can write them in a higher-level logic without resorting to writing the instructions yourself, as these can be quite complicated. We let the compiler do its thing, but guide it with a short f

wolfram77

Notes on the paper Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation.

wolfram77

Notes on the paper Joint Partitioning and Sampling Algorithm for Scaling Graph Neural Network.

wolfram77

See below.

wolfram77

Weather engineering architecture; Sahu (2024)

wolfram77

Fast and Efficient End-to-End Graph Processing with Shared Memory Accelerators; Mughrabi (2021)

Graph algorithms often require fine-grained, random access across substantially large data structures. Previous work on FPGA-based acceleration has required significant preprocessing and restructuring to transform the memory access patterns into a streaming format that is more friendly to off-chip hardware. However, the emergence of cache-coherent shared memory interfaces, such as Coherent Accelerator Processor Interface (CAPI), allows designers to more easily work with the natural in-memory organization of the data. This thesis introduces a vertex-centric shared-memory accelerator (AccelGraph) for graph algorithms optimized for high performance while effectively using coherent caching on the Field Programmable Gate Arrays (FPGA) hardware. The proposed design achieves speedups by selectively caching graph data for the accelerator while considering locality and reuse, compared to using the shared address space

wolfram77

DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication; Nunes et al. (2023)

Metrics for set similarity are a core aspect of several data mining tasks. To remove duplicate results in a Web search, for example, a common approach looks at the Jaccard index between all pairs of pages. In social network analysis, a much-celebrated metric is the Adamic-Adar index, widely used to compare node neighborhood sets in the important problem of predicting links. However, with the increasing amount of data to be processed, calculating the exact similarity between all pairs can be intractable. The challenge of working at this scale has motivated research into efficient estimators for set similarity metrics. The two most popular estimators, MinHash and SimHash, are indeed used in applications such as document deduplication and recommender systems where large volumes of data need to be processed. Given the importance of these tasks, the demand for advancing estimators is evident. We pro

wolfram77

Graph theory with applications; Bondy and Murty (1976)

wolfram77

Graph-Theoretic Problems and Their New Applications; Werner (2020)

Graph theory is an important area of Applied Mathematics with a broad spectrum of applications in many fields. In the Call for Papers for this issue, I asked for submissions presenting new and inoovative approaches for traditional graph-theoretic problems as well as for new applications of graph theory in emerging fields, such as network security, computer science and data analysis, bioinformatics, operations research, engineering and manufacturing, physics and chemistry, linguistics, or social sciences.

In response to the Call for Papers, we had an enormous resonance, and altogether 151 submissions have been received among which finally 20 papers have been accepted for this special issue, all of which are of high quality, reflecting the great interest in the area of Graph Theory. This corresponds to an acceptance rate of 13.2%. The authors of these accepted publications come from 13 different countries: USA, China, Pakistan, India, Ira