Abstrakt. Benchmarking graf-orienterad databas arbetsbelastning och graf-orienterade databassystem blir allt mer relevant i analytiska Big Data uppgifter, såsom sociala nätverk analys. I grafdata, struktur inte främst finns inne i noderna, men särskilt i sättet noder råkar vara ansluten, dvs.. Strukturella samband. Eftersom sådana strukturella korrelationer bestämma gå fläkt-outs erfarenhet av graf analys algoritmer och graf fråga exekutors, de är en väsentlig, men typiskt försummad, ingrediens i syntetiska grafgeneratorer. För att ta itu med detta presenterar vi S3G2: en skalbar struktur-korrelerad social grafgenerator. Denna grafgenerator skapar en syntetisk social graf, som innehåller icke-uniforma värdefördelningar och strukturella korrelationer, som är avsedd som testdata för skalbara grafanalysalgoritmer och grafdatabassystem. Vi generaliserar problemet med att bryta ner korrelerad grafgenerering i flera pass att varje fokus på en så kallad korrelation dimension, som var och en kan kartläggas till en MapReduce uppgift. Vi visar att S3G2 kan generera sociala grafer som (i) delar välkända graf konnektivitetsegenskaper som vanligtvis finns i verkliga sociala grafer (ii) innehåller vissa rimliga strukturella korrelationer som påverkar prestandan hos grafanalysalgoritmer och frågor, och (iii) kan snabbt genereras i enorma storlekar på vanliga kluster hårdvara. Data i verkliga livet är korrelerade, t.ex. Människor som bor i Tyskland har en annan fördelning i namn än människor i Italien (lokalisering), och människor som gick på samma universitet under samma period har en mycket högre sannolikhet att vara vänner i ett socialt nätverk. Sådana korrelationer kan starkt påverka den mellanliggande resultatstorleken av frågeplaner, effektiviteten av indexeringsstrategier, och orsaka frånvaro eller närvaro av lokalitet i data åtkomst mönster. När det gäller urvalsstorlekar för mellanliggande resultat, tänk på följande: SELECT personID FRÅN personen DÅ förnamn = 'Joachim' OCH adressLand = 'Tyskland' frågeoptimerare använder vanligen oberoende antagandet för att uppskatta resultatstorleken för konjunktiva predikat, genom att multiplicera uppskattningarna för de enskilda predikaten. Detta skulle underskatta denna resultatstorlek, eftersom Joachim är vanligare i Tyskland än i de flesta andra länder; liknande skulle t.ex. hända. när du frågar efter förnamn "Cesare" från "Italien". Överskattning kan också lätt ske, om vi skulle fråga efter "Cesare" från "Tyskland" eller "Joachim" från "Italien" (dvs. för att motverka korrelering). Detta korrelationsproblem har erkänts i relationsdatabassystem som relevant, och vissa arbeten finns för att upptäcka korrelerade egenskaper i samma tabell (t.ex., se [13] ). Ändå, att använda tekniker för att upptäcka korrelation är knappast mainstream i relationell databashantering, och detta är ännu mer så när vi börjar överväga samband mellan predikat som separeras av fogar. Betrakta till exempel DBLP exempel av co-authorship of papers som räknar antalet författare som har publicerat både i TODS och i VLDB Journal: SELECT COUNT( * ) FRÅN papper pa1 GÅ med tidskrift jn1 ON pa1.journal = jn1.ID papper pa2 GÅ med tidskrift jn2 ON pa2.journal = jn2.ID DOU PA1.author = pa2.författare OCH jn1.name = 'TODS' OCH jn2.name = 'VLDB Journal' Ovanstående fråga är sannolikt att ha en större resultatstorlek än en fråga som ersätter 'TODS' för 'Bioinformatics', även om Bioinformatics är en mycket större publikation än TODS. Den underliggande observationen är att databasforskare sannolikt kommer att sampublicera i TODS och The VLDB Journal, men är mycket mindre benägna att utföra tvärvetenskapligt arbete. För databasteknik, utgör detta exempel (i) en utmaning till optimizer att justera den uppskattade gå hit förhållandet pa1.author = pa2.författare nedåt eller uppåt beroende på andra (urval eller gå) predikerar i frågan (ii) ge indexering stöd som kan påskynda denna fråga: den anti-korrelerade fråga (Bioinformatics och The VLDB Journal) har en mycket liten resultatstorlek och kan därför teoretiskt besvaras mycket snabbt. Men att bara använda standardindex kommer att generera ett stort mellanresultat för Bioinformatics delplan som innehåller alla Bioinformatics författare, av vilka endast en liten bråkdel faktiskt är användbar för det slutliga svaret. Sammanfattande, korrelerade predikat är fortfarande ett gränsområde inom databasforskning, och sådana frågor är i allmänhet inte väl understötta ännu i mogna relationssystem. Detta håller ännu starkare i den framväxande klassen av grafdatabassystem, där vi hävdar att behovet av korrelation-medvetenhet i frågebehandling är ännu högre. I det särskilda fallet av RDF, dess grafdata modell är uttryckligen valt att fungera utan behov av en explicit schema, så att graf dataset lagras som en stor hög av kanter (särskilt, subjekt-egendom-objekt "triples"). Här ser vi en dualism mellan struktur och korrelation: i relationsmodellen är viss struktur explicit i schemat, medan en sådan struktur i RDF endast återuppstår som strukturell korrelation. Det vill säga, det kommer att visa sig en tidskrift tidning (ämne) alltid råkar ha en titel egendom, en utgåva egendom, en tidskriftNamn, etc; och att dessa egenskaper endast förekommer i samband med tidskriftsfrågor. Den extrema flexibiliteten hos RDF-system i de data de kan lagra, innebär därför en betydande utmaning för SPARQL frågeoptimerare, eftersom de behöver förstå sådana korrelationer för att få planeringen av även grundläggande frågor rätt. Andra diagram databassystem som använder en rikare datamodell, där noder har en deklarerad struktur, lider mindre av detta problem. Ändå, när man överväger att graf analys frågor ofta innebär en kombination av (fastighet) värde begränsningar och strukturella begränsningar (mönster matchning), är det troligt att korrelationer mellan strukturen av grafen och värdena i dem kommer att starkt påverka prestandan hos system och algoritmer. Systemen är dock inte tillräckligt medvetna om detta, och befintliga grafriktmärken testar inte specifikt detta, och syntetiska grafer som används för benchmarking har inte sådana strukturkorrelationer. Som sådan, vi hävdar att för benchmarking graf dataanalys system och algoritmer, skulle det vara mycket värt om en datagenerator skulle kunna generera syntetiska grafer som sådan korrelerad struktur. Enligt vår kunskap finns det ingen lösning för att generera en skalbar slumpmässig graf med värde- och strukturkorrelation. Befintlig litteratur om slumpmässig grafgenerering [4, 10, 6, 8] varken beaktar nodegenskaper alls eller ignorerar korrelationer mellan dem. I den här artikeln beskriver vi den skalbara strukturkorrelerade sociala grafgeneratorn (S3G2), och dess underliggande generiska konceptuella korrelerade grafgenereringsramverk. Detta ramverk organiserar datagenerering i flera faser som varje center runt en korrelationsdimension. I fallet med vår sociala grafanvändning är dessa dimensioner (i) utbildning och (ii) personliga intressen. Datagenereringsarbetsflödet begränsas av korrelationsberoenden, där vissa redan genererade data påverkar generering av ytterligare data. En grafgenerator genererar nya noder (med egenskapsvärden), och kanter mellan dessa noder och befintliga noder. Sannolikheten att välja ett visst värde från en ordbok, eller sannolikheten att ansluta två noder med en kant påverkas således av befintliga datavärden. Till exempel en persons födelseort påverkar sannolikhetsfördelningen av förnamn och universitetslexikon. Som ett annat exempel, sannolikheten att skapa en vänskap kant påverkas av (dis)överenskommelse om kön, födelseår och universitetsfastigheter av två person noder. En praktisk utmaning i S3G2 är att ett naivt tillvägagångssätt för korrelerad grafgenerering kontinuerligt skulle komma åt eventuellt någon nod och någon kant för att fatta beslut om generering av en nästa nod eller kant. För att generera grafer av en storlek som överstiger RAM, en sådan naiv algoritm skulle slipa ner på grund av dyra slumpmässiga I/O. För att ta itu med denna utmaning har vi utformat en S3G2 grafgenereringsalgoritm efter MapReduce paradigm. Varje passage längs en korrelationsdimension är en kartfas där data genereras, följt av en Reduce-fas som sorterar data längs den korrelationsdimension som styr nästa pass. Vi visar att denna algoritm uppnår bra parallell skala ut, vilket gör det möjligt t.ex. att inom en halvtimme generera 1,2 TB korrelerade grafdata på ett Hadoop-kluster på 16 maskiner. Bidragen från vårt arbete är följande: (1) Vi föreslår en ny ram för att specificera generering av korrelerade grafer, (2) vi visar nyttan av denna ram i sin förmåga att specificera generering av ett socialt nätverk med vissa rimliga korrelationer mellan värden och struktur, och (3) vi utformar en skalbar algoritm som implementerar denna generator som en serie av MapReduce uppgifter, och verifiera både kvaliteten på dess resultat samt dess skalbarhet. I vår vision, denna data generator är en viktig ingrediens för nya riktmärken för graf frågebehandling. Utgångspunkt. I Avsnitt 1 presenterar vi vår ram för generering av korrelerade grafer, och beskriver hur sådan det kartor på en MapReduce genomförande. I Avsnitt 2 använder vi vårt ramverk för att generera ett syntetiskt socialt nätverk diagram. I Avsnitt 3 utvärderar vi vår strategi, bekräftar att de genererade data har typiska sociala nätverksegenskaper, och visar skalbarheten hos vår generator. Äntligen, i avsnitt??, Vi granskar relaterade arbete innan vi avslutar i Avsnitt 4. Vi definierar först formellt slutprodukten av S3G2 som i huvudsak är en riktad graf av objekt, och introducera de viktigaste ingredienserna i S3G2 ramverket. Sedan beskriver vi MapReduce-baserad generationsalgoritm som följer av dessa ingredienser. S3G2 genererar en riktad markerad graf, där noderna är objekt med egenskapsvärden, och deras struktur bestäms av klassen en nod tillhör. En sådan datamodell tillhandahålls ofta av grafdatabassystem, och är mer strukturerad än RDF (även om den naturligtvis kan representeras i RDF, och vårt S3G2 genomförande i själva verket genererar RDF-utgång). Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. S3G2 producerar en graf G(V, E, P, C) där V är en uppsättning noder, E är en uppsättning kanter, P är en uppsättning egenskaper och C är en uppsättning klasser. är uppsättning av bokstavliga egenskaper av klass x i C; P E(x,y) är den uppsättning egenskaper som representerar relationskanter som går från fall av klass x till klass y. Vi diskuterar nu den konceptuella ramen bakom S3G2, som är (i) egendom ordböcker, (ii) enkel subgraph generation, och (iii) kantgenerering längs korrelation dimensioner. L(x) skapas efter en egenskap ordbok specifikation P D l (D, R, F ), bestående av en ordbok D, en ranking funktion R och en sannolikhetsfunktion F (om sammanhanget är oklart, kan vi också skriva D l, R l och F l ). Ett lexikon D är helt enkelt en fast uppsättning värden: D = {v 1,.., v  på D}. Rankningsfunktionen R är en bijection R : D → {1,..,  på D} som ger varje värde i en ordbok en unik rankning mellan 1 och  på D. Sannolikhetstäthetsfunktionen F : {1,..,  på D} →[0, 1] styr hur generatorn väljer värden; d.v.s. Genom att ha den rita slumptal 0 ≤ p ≤ 1, väljer den den största rank r sådan att den slutligen avger värdet v pos från ordbok D från position pos = R(r). På så sätt kan vårt ramverk generera data som motsvarar varje diskret sannolikhetsfördelning. Tanken att ha en separat ranknings- och sannolikhetsfunktion kommer från att generera korrelerade värden. Särskilt rankningsfunktionen R[z](c) parametriseras normalt av vissa parametrar z; vilket innebär att värderankningen är annorlunda beroende på parametern z. I fallet med en ordbok med förnamn kan vi till exempel ha R [t.ex. c, y]; t.ex. populariteten av förnamn, beroende på kön g, land c och året y från födselnDate egendom (låt oss kalla detta födelseår). Således, det faktum att populariteten av förnamn i olika länder och tider är olika, återspeglas av de olika leden som produceras av funktion R() över den fullständiga ordboken av namn. Namn frekvensfördelning tenderar att vara liknande i form, vilket garanteras av det faktum att vi använder samma sannolikhetsfördelning F () för alla uppgifter om en fastighet. Således måste S3G2 datageneratorn innehålla egendom ordböcker D l för alla bokstavliga egenskaper i l  på L (x), och det måste också innehålla rankningsfunktionerna R l, för alla bokstavliga egenskaper som definieras i alla klasser x  på C. När korrelationsparametrar för en beställningsfunktion R l, bör man se till att mängden parameterkombinationer såsom (g, c, y) förblir begränsad, för att hålla representationen av sådana funktioner kompakt. Vi vill att generatorn ska vara ett relativt litet program och inte vara beroende av enorma datafiler med ordböcker och rankingfunktioner. Figur 2 visar hur S3G2 kompakt representerar R [g, c, y], genom att hålla för varje kombination av (g, c, y) en liten tabell med endast topp-N ordboksvärden (här N = 10 för presentationsändamål, men det är typiskt större). Snarare än att lagra en beställning av alla värden, en tabell som R [manlig, Tyskland, 2010] är bara en rad N heltal. Ett värde j här identifierar helt enkelt värdet v j i ordbok D. Den här tabellen lagrar alltså bara de topp-N-rankade värdena. För att undvika att lagra mer information, de värden rankas lägre än N få sina led tilldelas slumpmässigt. Med tanke på att i en monotont minskande sannolikhet funktion som den geometriska fördelning som används här, sannolikheterna under den rank är mycket liten ändå, denna approximation minskar endast något rimligheten av de genererade värdena. I figur 2 ser vi till vänster att för (man, Tyskland,2010) behåller vi de 10 mest populära pojknamnen, som kartläggs på den geometriska fördelningen. Alla andra ordlista värden (bland vilka italienska namn) få några slumpmässiga leden > 10. Till höger ser vi att för (manliga,Italien,2010) dessa italienska namn är faktiskt de mest populära, och de tyska namnen får godtyckliga (och låga) sannolikheter. Enkel grafgeneration. Kanter genereras ofta i en gå tillsammans med nya noder, i huvudsak börjar med en befintlig nod n, och skapa nya noder som den blir ansluten till. Denna process styrs av en gradfördelningsfunktion N (n) som först bestämmer hur många sådana nya barn (eller ättlingar) som ska genereras. I många sociala nätverk fördelas mängden grannkanter h efter en maktfördelning (N (h)  och γ.h −λ ). Inom ramen för S3G2 är det möjligt att göra funktionen N (n i ) som bestämmer graden av en nod n i korrelerad med dess egenskaper, t.ex. genom att ha dessa egenskaper påverkar λ eller γ. Till exempel, människor med många vänner i ett socialt nätverk kommer vanligtvis att lägga upp fler bilder än människor med få vänner (därav, mängden av vän noder i vår användning fall påverkar mängden postade kommentarer och bild noder). Skapa nya noder och ansluta dem på flugan bland mestadels själva och till en befintlig nod n i leder till isolerade subgrafer som dinglar av huvudgrafen ansluten till det av n i. Vanligtvis är sådana subgrafer små eller har formen av grunda träd om de är större. Korrelationsmått. För att generera korrelerade och starkt anslutna grafdata behöver vi ett annat tillvägagångssätt som genererar kanter efter att ha genererat många noder. Detta är beräkningsmässigt svårare än att generera kanter mot nya noder. Anledningen är att om nodegenskaper påverkar deras anslutning, skulle ett naivt genomförande behöva jämföra egenskaperna hos alla befintliga noder med alla noder, vilket kan leda till kvadratiska beräkningskostnader och ett slumpmässigt tillträdesmönster, så generationsalgoritmen skulle bara vara snabb så länge data passar i RAM. Data korrelation lindrar faktiskt detta problem. Vi observerar att sannolikheten att två noder är anslutna är typiskt skev med avseende på viss likhet mellan noderna. Eftersom node n i, för en liten uppsättning noder som på något sätt liknar den, det finns en hög anslutning sannolikhet, medan för de flesta andra noder, är denna sannolikhet ganska låg. Denna observation kan utnyttjas av en grafdatagenerator genom att identifiera korrelationsdimensioner. För en viss kant etikett e  på P E (x,y), så en enda metrisk funktion skulle normalt användas. För enkelhetens skull kommer vi att anta M = M x = M y i uppföljaren. Vi kan beräkna likheten metriska genom att åberopa M (n i ) på alla noder n i, och sortera alla noder på denna poäng. Detta innebär att liknande noder förs nära varandra, och vi observerar att ju större avståndet mellan två noder, deras likhet skillnad monotoniskt ökar. Återigen använder vi en geometrisk sannolikhetsfördelning för F () som ger en sannolikhet för att plocka noder att ansluta med som är mellan 1 och W.t positioner isär i denna likhet ranking. För att helt uppfylla en geometrisk fördelning, bör vi inte förkorta vid W.t positioner isär, men överväga ännu ytterligare isär noder. Men vi observerar att för en skev fördelning som geometrisk, sannolikheten många positioner bort kommer att vara minut, dvs... ≤ ε (F (W.t) = ε). Fördelen med denna fönstergenväg är att efter sortering av data, det tillåter S3G2 att generera kanter med hjälp av en helt sekventiell åtkomst mönster som behöver lite RAM-resurser (det bara buffertar W.t noder). Ett exempel på en likhetsfunktion M () kan vara placering. Plats, d.v.s. ett platsnamn, kan kartläggas till (longitud, latitud) koordinater, men för M () behöver vi ett endimensionellt mått som kan sorteras på. I detta fall kan man hålla (longitud, latitud) på 16-bitars heltal upplösning och blanda dessa genom bit-genomföring i en 32-bitars heltal. Detta skapar en tvådimensionell rymdfyllningskurva kallad Z-ordning, även känd i geografisk frågebehandling som QuadTiles 3. En sådan utrymme fylla kurvan "i stort sett" ger egenskapen att punkter som är nära varandra i Euclidean utrymme har en liten z-ordning skillnad. Observera att användningen av likhetsfunktioner och sannolikhetsfördelningsfunktioner över rankad distansenhet vilken typ av noder får koppling med en kant, inte hur många. Beslutet om graden av en nod görs innan man skapar kanterna, med hjälp av den tidigare nämnda examen funktion N (n i ), som i sociala nätverk normalt skulle vara en makt-law funktion. Under datagenerering uppfylls denna grad av node n i genom att slumpmässigt välja det antal kanter som krävs enligt den korrelerade sannolikhetsfördelning som beskrivits tidigare i exemplet med person som har många vänner som genererar fler diskussionsinlägg. Vid flera korrelationer, och därmed flera passerar längs korrelation dimensioner, bestämmer vi för varje passera antalet kanter för att generera för en viss nod. Den övergripande gradfunktionen N (n) = N CD (n) är summan av gradfördelningsfunktionerna över alla korrelationsmått CD. Slumpmässig dimension. Tanken att vi bara genererar kanter mellan W.t mest liknande noder i alla korrelation dimensioner är alltför restriktiv: osannolika anslutningar i ett socialt nätverk som datamodellen inte skulle förklara eller göra rimlig, kommer att inträffa i praktiken. Sådana slumpmässiga buller kan modelleras genom att delvis falla tillbaka på enhetlig slumpmässig datagenerering. I ramen för S3G2 kan detta modelleras som ett specialfall av en korrelationsdimension, genom att använda en rent slumpmässig funktion som grov metrisk, och en enhetlig sannolikhetsfunktion. Därför kan datadistributioner göras mer bullriga genom att göra ett pass i slumpmässig ordning över data och generera (ett fåtal) ytterligare slumpmässiga kanter. I den föregående diskussionen har vi introducerat huvudbegreppen i ramen för S3G2: (i) korrelerade datalexikon (ii) enkel grafgenerering (iii) kantgenerering enligt korrelationsmått. Vi beskriver nu hur en MapReduce-algoritm byggs med hjälp av dessa ingredienser. 3 Se http://wiki.openstreetmap.org/wiki/QuadTiles Tile som fylls Fönster för W senaste brickor Tile för t noder nod för vilka kanter genereras Bild. 3............................................................... Glidande fönster av W kakel längs grafen.
Social Intelligence BenchMark (SIB) REF är ett RDF-riktmärke som introducerar S3G2 (Scalable Structure-korrelated Social Graph Generator) för att generera sociala grafer som innehåller vissa strukturella korrelationer.
S3G2: A Scalable Structure-Correlated Social Graph Generator
{'venue': 'Lecture Notes in Computer Science', 'journal': 'Lecture Notes in Computer Science', 'mag_field_of_study': ['Computer Science']}