We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Concurrent data structures: CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure

00:00

Formal Metadata

Title
Concurrent data structures: CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure
Title of Series
Number of Parts
30
Author
License
CC Attribution 4.0 International:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
The graph model enables a broad range of analysis, thus graph processing is an invaluable tool in data analytics. At the heart of every graph-processing system lies a concurrent graph data structure storing the graph. Such a data structure needs to be highly efficient for both graph algorithms and queries. Due to the continuous evolution, the sparsity, and the scale-free nature of real-world graphs, graph-processing systems face the challenge of providing an appropriate graph data structure that enables both fast analytic workloads and low-memory graph mutations. Existing graph structures offer a hard trade-off between read-only performance, update friendliness, and memory consumption upon updates. In this paper, we introduce CSR++, a new graph data structure that removes these trade-offs and enables both fast read-only analytics and quick and memory-friendly mutations. CSR++ combines ideas from CSR, the fastest read-only data structure, and adjacency lists to achieve the best of both worlds. We compare CSR++ to CSR, adjacency lists from the Boost Graph Library, and LLAMA, a state-of-the-art update-friendly graph structure. In our evaluation, which is based on popular graph-processing algorithms executed over real-world graphs, we show that CSR++ remains close to CSR in read-only concurrent performance (within 10% on average), while significantly outperforming CSR (by an order of magnitude) and LLAMA (by almost 2x) with frequent updates.
Graph (mathematics)System programmingGraph theoryRead-only memoryRead-only memoryVertex (graph theory)Insertion lossSparse matrixDirac delta functionElectronic mailing listStapeldateiInsertion lossData structureElectronic mailing listGraph (mathematics)Core dumpOperator (mathematics)Food energyShooting methodPhysical lawGrass (card game)Category of beingArithmetic meanHypermedia1 (number)Mathematical optimizationNumberTerm (mathematics)Ocean currentTwitterSinc functionMachine vision2 (number)Instance (computer science)Bit rateSocial classDemosceneSemiconductor memoryGraph (mathematics)Green's functionMathematicsContext awarenessNumbering schemeMassWave packetAreaRepresentation (politics)Data storage deviceGraph theoryStapeldateiReal numberAutonomous System (Internet)Library (computing)Physical systemVertex (graph theory)Process (computing)Endliche ModelltheorieTheory of relativityPerformance appraisalAlgorithmAnalytic setRead-only memoryOrder of magnitudeDirac delta functionCollaborationismProof theoryStudent's t-testCompact spaceWorkloadArray data structureBitWeb pageComputer animation
Performance appraisalComputer fontGraph theoryCompact spaceArray data structureGraph (mathematics)Vertex (graph theory)Electronic mailing listCongruence subgroupCache (computing)Inclined planeFlow separationPlastikkarteResource allocationContinuous functionConcurrency (computer science)Arithmetic meanSemiconductor memoryGraph (mathematics)Graph (mathematics)Vertex (graph theory)Degree (graph theory)Compact spaceArray data structureSinc functionMathematical optimizationResource allocationPointer (computer programming)Electronic mailing listCASE <Informatik>PlastikkarteAnalytic continuationData structureMathematical analysisAreaLocal ringGraph theoryCategory of beingCommunications protocolFile formatSynchronizationCombinational logicNumberMechanism designData storage deviceInstance (computer science)WordWave packetRight angleForm (programming)Doubling the cubeMedical imagingFormal languageGoodness of fitGroup actionPlanningMultiplication signComputer animation
PlastikkarteContinuous functionResource allocationGraph (mathematics)Vertex (graph theory)LengthElectronic mailing listArray data structureGraph (mathematics)Pointer (computer programming)FlagStatement (computer science)Row (database)WritingGraph (mathematics)Vertex (graph theory)SynchronizationNumberCategory of beingPointer (computer programming)Series (mathematics)Medical imagingRight angleComputer animationDiagram
Graph (mathematics)Pointer (computer programming)VortexVertex (graph theory)LengthGraph (mathematics)FlagSemiconductor memoryCategory of beingPointer (computer programming)Vertex (graph theory)Goodness of fitNumberArray data structureDegree (graph theory)LengthGraph (mathematics)Arithmetic meanWave packetTorusComputer animation
LengthVertex (graph theory)Graph (mathematics)Graph (mathematics)Limit (category theory)Graph (mathematics)Field (computer science)Graph (mathematics)Electronic mailing listVertex (graph theory)Subject indexingArithmetic meanMultiplication signData storage deviceCategory of beingLine (geometry)Computer animation
Graph (mathematics)Array data structureParalleler AlgorithmusRead-only memoryResource allocationVertex (graph theory)Pointer (computer programming)Insertion lossCommunications protocolCategory of beingVertex (graph theory)Category of beingGraph (mathematics)Array data structureSubject indexingPointer (computer programming)Data storage deviceLatent heatWell-formed formulaArithmetic meanSlide ruleCommunications protocolParalleler AlgorithmusInsertion lossMetropolitan area networkSampling (statistics)Direction (geometry)Wave packetWordSingle-precision floating-point formatInstance (computer science)Computer animation
Pointer (computer programming)Array data structureCommunications protocolVertex (graph theory)Insertion lossCategory of beingResource allocationGraph (mathematics)StapeldateiContext awarenessMultiplicationThread (computing)LengthFlagConditional probabilityGraph theoryGraph (mathematics)AlgorithmElectronic mailing listLibrary (computing)Cache (computing)Configuration spacePerformance appraisalTwitterGreen's functionRankingWeb pageVirtual machineWeight functionVertex (graph theory)TrailReal numberCASE <Informatik>Degree (graph theory)Context awarenessGraph (mathematics)Configuration spaceSystem programmingPointer (computer programming)Compact spaceArray data structureCategory of beingMathematical analysisInteractive televisionFlagConcurrency (computer science)SpacetimeLogicData structureBranch (computer science)Insertion lossMultiplication signPerformance appraisalCommunications protocolArithmetic meanGraph (mathematics)Traverse (surveying)Field (computer science)LengthThread (computing)UsabilityDirection (geometry)System callPoint (geometry)Physical lawGrass (card game)Group actionMathematicsBit rateData miningShared memoryArithmetic progressionMedical imagingExecution unitFood energyConnectivity (graph theory)Line (geometry)Ext functorRight angleFlow separationSheaf (mathematics)Operator (mathematics)19 (number)AreaSemiconductor memoryTwitterComputer animation
Graph theoryAlgorithmGraph (mathematics)Electronic mailing listLibrary (computing)Cache (computing)Configuration spacePerformance appraisalVertex (graph theory)Green's functionTwitterWeb pageRankingVirtual machineWeight functionGraph (mathematics)RankingTwitterWeb pageWeightGraph theoryConnectivity (graph theory)Wave packetLibrary (computing)CodeAlgorithmWorkloadVirtual machineElectronic mailing listOpen sourceImplementationCore dumpNetwork socketEvent horizonPhysical lawComputer animation
Web pageRankingThread (computing)TwitterScalabilityOverhead (computing)TwitterLine (geometry)Data structureRead-only memoryGraph theoryScalabilityComputer animationDiagram
Thread (computing)ScalabilityWeb pageRankingTwitterOrder of magnitudeGraph (mathematics)Insertion lossOrder of magnitudeGraph theoryNumberGraph (mathematics)Thread (computing)Sign (mathematics)TrailGrass (card game)Arithmetic meanInsertion lossVertex (graph theory)Operator (mathematics)Form (programming)Term (mathematics)Instance (computer science)IntegerSurgeryComputer animationDiagram
Order of magnitudeGraph (mathematics)Insertion lossStapeldateiThread (computing)Read-only memoryTwitterRead-only memoryOverhead (computing)Scale (map)Resource allocationDivisorArray data structureGraph (mathematics)ScalabilityConcurrency (computer science)AverageAnalytic setPhysical lawMatching (graph theory)2 (number)Data structureOverhead (computing)Graph (mathematics)Stability theorySemiconductor memoryInsertion lossMultiplication signGraph (mathematics)StapeldateiContext awarenessSpacetimeAreaOrder of magnitudeCASE <Informatik>Graph theoryConcurrency (computer science)Arithmetic meanRead-only memoryElectronic mailing listSystem programmingScalabilitySoftware testingInternet forumAverageWindowLetterpress printingSocial classMedical imagingCircleArmMechatronicsStudent's t-testComputer animation
Graph (mathematics)ScalabilityConcurrency (computer science)Analytic setAverageOverhead (computing)Read-only memoryComputer animation
Transcript: English(auto-generated)