O¨ zet Sosyal ag˘lara giderek artan ilgi, beraberinde bu¨yu¨k o¨lc¸eklerde bag˘lantılı veri ac¸ıg˘a c¸ıkarmı¸stır. Bu bu¨yu¨k veriler u¨zerinde arama yapabilmek ic¸in ¨ozelle¸stirilmi¸s sistemlere gereksinim duyulmaktadır. Bu gereksinimi kar¸sılamak u¨zere Facebook, 2013 yılında kendi arama motoru olan Unicorn'u[1] hizmete sunmu¸stur. Bu c¸alı¸smada, Unicorn'un asgari fakat temel o¨zellikleri tasarlanıp gerc¸ekle¸stirilmi¸stir. Yakla¸sımımızda sosyal ag˘ bir ¸cizge olarak modellenmi¸stir ve c¸izgedeki du¨g˘u¨mler ve kenarlar farklı tu¨rlere sahip olabilecek ¸sekilde genel olarak tanımlanmı¸stır. Du¨g˘u¨mler, ki¸si veya sayfa gibi varlıkları ifade ederken; kenarlar, du¨g˘u¨mler arasındaki arkada¸slık veya beg˘enme ili¸skisini ortaya koyar. Verimlilik sorununu ¸co¨zebilmek ic¸in tamamen bellek u¨zerinde c¸alı¸san bir indisleme sistemi geli¸stirilmi¸stir. Bu sistem geni¸s o¨l¸cekte veri i¸slenmesini sa˘glamak u¨zere geli¸stirilen da˘gıtık motor Spark[2] u¨zerinde ger¸cekle¸stirilmi¸stir. Son olarak, sosyal ag˘ yapısına uygun i¸sle¸cler (ve, veya, zayıf- ve, gu¨c¸lu¨-veya, uygula) tasarlanmı¸stır. Bu i¸slec¸ler sayesinde kolayca ki¸silerin ortak arkada¸sları veya arkada¸slarının arkada¸sları gibi sorgular ifade edilip c¸alı¸stırılabilmektedir. C¸alı¸smanın son bo¨lu¨mu¨nde bu tip bir sistemin gerc¸ekle¸stirilmesinde dikkate alınması gereken nitelikler, bu niteliklere ili¸skin o¨du¨nle¸simler ve karar mekanizmaları ele alınıp deg˘erlendirilmi¸stir.
Facebook 2013 yılında yeni c¸izge arama motoru Unicorn’u aktif hale getirmi¸stir. Unicorn, sosyal ¸cizgedeki yapılandırılmı¸s veri u¨zerinde hızlı ve ¨ol¸ceklenebilir bir ¸sekilde arama yapmayı ve arama sonuc¸ları u¨zerinde gereksinimler do˘grultusunda karma¸sık i¸sle¸cler c¸alı¸stırmayı sa˘glayan ¨ozel bir tasarıma sahiptir.
Unicorn temelde bir bilgi elde etme sistemidir, sosyal a˘g verisini i¸slemek u¨zere ¨ozelle¸smi¸stir. Sosyal ¸cizge verisine eri¸smek ve veriyi sıralamak ic¸in etkin bir veri yapısı mevcuttur ve bu yapı u¨zerinde ¸calı¸stırılacak sorgu tasarımı ve ger¸cekle¸stirimi fonksiyonel programlama dillerindeki liste i¸sleme altyapısı ve fonksiyonları ile yapılmı¸stır. Sistem bu sayede binlerce sunucu u¨zerinde tutulan du¨˘gu¨mler (kullanıcılar ve dig˘er varlıklar) arasındaki trilyonlarca kenar u¨zerinde etkin bir ¸sekilde arama yapabilmektedir.
Bu ¸calı¸smada, Unicorn’un c¸ekirdek arama motoru geli¸stirilmi¸stir. Geli¸stirilen yazılım Unicorn’un asgari fakat temel ¨ozelliklerini kapsamaktadır. Unicorn’un karma¸sık sistem mimarisine odaklanmak yerine bellek u¨zerinde indisleme, farklı kenar ve du¨˘gu¨m tiplerini destekleyen c¸izge veri yapısı olu¸sturma, veri sıralama stratejileri ve arama sonu¸cları u¨zerinde da˘gıtık bir ¸sekilde c¸alı¸stırılabilen karma¸sık i¸sle¸cler gerc¸ekle¸stirilmi¸stir. Bu temel ¨ozellikler bu¨yu¨k ¨olc¸ekli sosyal ¸cizge arama motorunun altyapısını olu¸sturmaktadır.
Geli¸stirilen sistemde dag˘ıtık veri i¸sleme motoru Spark kullanılmı¸stır. C¸ alı¸smada aynı zamanda s¨ozkonusu temel ¨ozelliklerin ger¸cekle¸stirimi sırasında kar¸sıla¸sılan o¨du¨nle¸simler ve ilgili karar mekanizmaları u¨zerine bir de˘gerlendirme yapılmı¸stır.
Sosyal ¸cizge verisini i¸slemek u¨zere ¨ozelle¸smi¸s arama motoru gerc¸ekle¸stiriminde
ilk olarak u¨zerinde c¸alı¸sılacak bu¨yu¨k sosyal c¸izge verisi belirlenmi¸stir. SNAP[
Arama motorlarında d¨ondu¨ru¨len sonuc¸ların sıralanması (ranking) temel i¸slevlerden
bir tanesidir. Sıralama yapmak u¨zere farklı ¨olc¸u¨tler kullanılabilir. Gerc¸ekle¸stirdi˘gimiz
yapı i¸cerisinde belli bir ¨olc¸u¨te g¨ore sonuc¸ları sıralı tutma gereksinimini de kar¸sılamak
u¨zere sıralama ¨ol¸cu¨tu¨ olarak du¨g˘u¨mlerin PageRank[
Sosyal ¸cizge arama motoru, anlambilimsel ¸cizgeler u¨zerinde i¸slem ger¸cekle¸stirebilir.
Anlambilimsel ¸cizgelerde du¨g˘u¨mler ve kenarlar anlamsal etiketlere sahiptir. Bir
ba¸ska ifade ile farklı du¨˘gu¨m ve kenar tipleri bulunabilmektedir. SNAP
verisetinden sa˘glanan c¸izgelerde sadece tek tip du¨g˘u¨m ve kenar bulundug˘undan Yelp
Academic Dataset Challenge’dan[
Gerekli veri toplanıp analiz edildikten sonra sosyal c¸izge kom¸suluk listesi yakla¸sımı kullanılarak Spark u¨zerinde farklı du¨g˘u¨m ve kenar tiplerini destekleyecek ¸sekilde gerc¸ekle¸stirilmi¸stir. Tanımlanan farklı tipler herhangi bir varlıg˘ı veya ili¸skiyi temsil edebilece˘ginden genel (generic) bir ¸cizge yapısı kurulmu¸stur. Kom¸suluk listeleri, kenar tipi-ID ikilileri kullanılarak indislenmi¸stir.
Bu sayede, bir kullanıcının arkada¸sları ya da bir sayfanın beg˘enenleri gibi verilere kısa su¨rede ula¸sılabilir. Sosyal c¸izge g¨orseli ¸sekil 1’de verilmektedir.
S¸ekil 1. Sosyal c¸izge.
Unicorn makalesinde anlatılan i¸slec¸ler Spark u¨zerinde da˘gıtık ve paralel olacak ¸sekilde ger¸cekle¸stirilmi¸stir. I˙¸sle¸cler sayesinde veri ku¨mesine ait c¸izgeden pek c¸ok farklı sorgu ¸sekli u¨retilebilir.
Yelp’ten elde edilen veri ku¨mesi ic¸inde pek c¸ok farklı varlık ve ili¸ski tipi bulunması ve bu varlık ve ili¸skileri tanımlayıcı karakter dizilerinin (so¨zcu¨klerin) de mevcut olması bu karakter dizilerini temel alan ters dizinlerin yaratılmasını mu¨mku¨n hale getirmi¸stir. Sonuc¸ olarak, c¸izge u¨zerinde karakter dizisi ile de arama yapılabilmektedir. O¨ rne˘gin, ”Jon” ismine sahip kullanıcılar elde edilebilir.
Son olarak, typeahead arama ¨ozellig˘i ger¸cekle¸stirilmi¸stir. Bu sayede, arama sorgusu s¨ozcu¨˘gu¨n ilk karakteri girildi˘gi andan itibaren ¸calı¸stırılabilir ve bu karakter ile ba¸slayan sonu¸clara eri¸silebilir. Geli¸stirilen ters dizin ¸seması buna uygun hale getirilmi¸stir.
Kom¸suluk listeleri hem kenar tipi-ID ikilileri hem de ters dizin u¨zerinden indislenmi¸stir. Kenar tipi-ID ikilisi temelli indisleme ¸cizgede kenarlar u¨zerinde hareket edilmesini sa˘glar, ¨orne˘gin bir kullanıcının arkada¸slarının bulunması. Ters dizin yapısı ise belli bir karakter dizisini ic¸eren du¨g˘u¨mlerin do¨ndu¨ru¨lmesini destekler.
Kom¸suluk listesindeki her eleman Hit olarak adlandırılır ve Hit’ler DocId ve sec¸meli HitData bayt dizisinden olu¸smaktadır. DocId’ler ondalıklı sort-key ve 32bit tamsayı id ikilisinden meydana gelmektedir. Sort-key her du¨g˘u¨mu¨n sıralama o¨lc¸u¨tu¨ne go¨re aldıg˘ı de˘geri (sistemimizde PageRank de˘geri), id ise du¨g˘u¨m kimli˘gi bilgisini kar¸sılamaktadır. Kom¸suluk listesi ¨orne˘gi ¸sekil 2’de verilmektedir: List = {Hit1, Hit2, Hit3, · · · , Hitn}
Hit = (DocId, HitData)
DocId = (SortKey, Id) sort-key id 65 58 63 64 23 26 22 13 22 55 13 43
S¸ekil 2. Kom¸suluk Listesi Veri Yapısı: Listeler o¨nce bu¨yu¨kten ku¨c¸u¨g˘e sort-key’e go¨re daha sonra ku¨c¸u¨kten bu¨yu¨g˘e id’ye go¨re sıralanmı¸stır. Bo¨ylece, sırası daha yu¨ksek olan du¨g˘u¨mler kırpma olmadan i¸slenebilir ve ayrıca yu¨ksek sıralı olanların o¨nce g¨osterilmesi arama motoru sıralama o¨zellig˘ine uygundur. Sosyal c¸izge, Spark u¨zerinde kom¸suluk listeleriyle dag˘ıtılmı¸stır. Yani, ¸sekildeki liste bir kullanıcının ilk parc¸a u¨zerindeki arkada¸sları ise, aynı kullanıcının ikinci ve dig˘er parc¸alarda da arkada¸slarının bir kısmı barınıyor olabilir. Bu ¸sekilde bir dag˘ıtım, o¨lu¨ bir makine oldug˘u zaman hic¸bir ¸sey go¨stermemektense kullanıcının arkada¸slarının bir kısmını go¨stermeyi mu¨mku¨n kılar.
I˙¸sle¸cler sosyal ¸cizgedeki bilgiye eri¸sim sa˘glamak ic¸in tasarlanıp ger¸cekle¸stirilmi¸stir. Bu i¸slec¸ler, term, and (ve), or (veya), weak-and (zayıf-ve), strong-or (gu¨¸clu¨-veya) ve apply (uygula) i¸sle¸cleridir. O¨ nek simgelemi g¨osterimindeki i¸slec¸lerin sonsuz sayıda zincirlenebilmesi i¸cin i¸sle¸cler Composite Design Pattern kullanılarak tasarlanmı¸stır. term i¸sleci bir du¨˘gu¨me kom¸su olan du¨˘gu¨m listesine veya bir karakter dizisini ic¸inde barındıran du¨˘gu¨mlere eri¸simi sa˘glar: ( term f r i e n d : 5 ) 5 ID’li kullanıcının arkada¸sları. Michael so¨zcu¨˘gu¨nu¨ barındıran du¨˘gu¨mler. and (ve) i¸sleci kom¸suluk listelerinin kesi¸sim ku¨mesinin hesaplanmasını sa˘glar. Bu i¸slece ait kod algoritma 1’de verilmi¸stir.
Algorithm 1 Liste kesi¸simi, ¨ozyinelemeli prosedu¨r (intersectRec) kullanılarak ger¸cekle¸stirilmi¸stir. Algoritma, intersect prosedu¨ru¨nu¨n, intersectRec prosedu¨ru¨nu¨ son parametresi bo¸s bir liste olacak ¸sekilde c¸a˘gırması ile ba¸slar. Daha sonra, her iki listenin ilk elemanlarından ba¸slanarak, Hit’lerin docId ikililerinin e¸sitlikleri kar¸sıla¸stırılır ve eg˘er e¸sit iseler, her iki listenin geriye kalan elemanları kar¸sıla¸stırılan eleman sonuc¸ listesine sondan eklenerek, eg˘er biri di˘gerinden ku¨c¸u¨k ise, ku¨c¸u¨k olan listenin geri kalanı, di˘ger listenin tamamı ve sonu¸c listesi de˘gi¸stirilmeden prosedu¨r ¨ozyinelemeli olarak c¸a˘grılır. 1: procedure intersect(l1, l2) 2: return intersectRec(l1, l2, emptyList) 3: end procedure 4: procedure intersectRec(l1, l2, r) 5: if l1 == empty or l2 == empty then 6: return r 7: if l1.head.docId == l2.head.docId then 8: return intersectRec(l1.tail, l2.tail, r.append(l1.head)) 9: 10: if l1.head.docId < l2.head.docId then
return intersectRec(l1.tail, l2, r) 11: return intersectRec(l1, l2.tail, r) 12: end procedure or (veya) i¸sleci kom¸suluk listelerinin birle¸sim ku¨mesinin hesaplanmasını sa˘glar. ( o r ( f r i e n d : 5 ) ( f r i e n d : 6 ) ) 5 ve 6 ID’li kullanıcıların arkada¸sları. weak-and (zayıf-ve) i¸slecinin ve i¸slecinden tek farkı sec¸meli sayı ve a˘gırlık parametrelerini kullanıyor olmasıdır. Bu parametreler sayesinde, zayıf-ve i¸slecinin sonu¸c listesinde olabilmek ic¸in parametre eklenmi¸s olan i¸slecin sonuc¸ listesinin bu i¸slecin kar¸sıla¸stırıldıg˘ı i¸slecin sonuc¸ listesinin tamamı ile kesi¸smesi gerekmemektedir. Yani sıra de˘geri yu¨ksek olan Hit’lerin belli bir kısmında kesi¸sme ko¸sulu aranmayabilir. ( weak−and ( f r i e n d : 5 : opt−w e i g h t 0 . 1 ) ( term ” m i c h a e l ” ) ) 5 ID’li kullanıcının Michael isimli arkada¸sları. (term ”michael”) sonu¸c listesindeki Hit’lerin sonuca yansıması i¸cin, (friend:5) sonu¸c listesindeki Hit’lerin yu¨zde 10’u ile kesi¸smesi gerekmez. strong-or (gu¨c¸lu¨-veya) i¸sleci kırpma sonucu tamamen kaybolabilecek du¨¸su¨k sıra de˘gerlerine sahip bir i¸slec¸ sonucunun, sonuc¸ listesinin bir kısmını kesinlikle olu¸sturmasını garanti eder. ( s t r o n g −o r ( l i v e −i n : 1 0 0 ) ( l i v e −i n : 1 0 1 : opt−w e i g h t 0 . 1 ) ) 101 ID’li ¸sehirde ya¸sayan kullanıcıların, sonu¸c listesinin yu¨zde 10’unda bulunması garanti edilmi¸stir. apply (uygula) i¸sleci sosyal ¸cizgede bir kenardan ¨oteye ula¸sılmasını sa˘glar. apply i¸sleci gerc¸ekle¸stirimi algoritma 2’de verilmi¸stir. ( a p p l y f r i e n d : ( f r i e n d : 5 ) ) 5 ID’li kullanıcının arkada¸slarının arkada¸sları. (friend:5) i¸slecinden gelen listenin her bir elemanının arkada¸slarının bile¸sim ku¨mesi sonu¸c olur. Algorithm 2 Apply algoritması bir kenar-tipi ve i¸sleci parametre olarak alır. Parametre olan i¸sle¸c ¸calı¸stırılır ve sonuc¸ listesindeki bu¨tu¨n Hit’lerin ID’leri ve parametre olan kenar-tipi kullanılarak yeni term i¸sle¸cleri, belirlenmi¸s olan bir limit sayısı kadar olu¸sturulup bir listeye atılır. Daha sonra bu liste bir or i¸slecine parametre olacak ¸sekilde verilir ve c¸alı¸stırılıp sonuc¸ olarak do¨ndu¨ru¨lu¨r. 1: procedure apply(eT ype, operator) 2: applyLimit ← 50 3: rAdjList ← operator.execute() 4: termList ← emptyList 5: for i ← 0; i < applyLimit do 6: id ← rAdjList[i].docId.id 7: termList.append(T erm(eT ype, id)) 8: end for 9: return Or(termList).execute() 10: end procedure
Ters dizinler belli bir karakter dizisini ic¸eren du¨g˘u¨mlere eri¸silmesini sa˘glar. Bu indisler yolu ile ismi ”Carl” olan kullanıcılar veya kategorisi ”fast-food” olan restoranlar hızlı bir ¸sekilde bulunabilir. Ters dizinlerin arkasındaki du¨¸su¨nce sosyal c¸izgeyi indislerken kullanılanla aynıdır. Tek fark indisin kenar tipi-ID ikilisi de˘gil, bir karakter dizisi olmasıdır. I˙ndislenmi¸s olan liste yine Hit’lerden olu¸sur ve Hit’lerin indisleyen karakter dizisini ic¸erdi˘gi kesindir. Standart bilgi elde etme sistemlerinde s¨ozcu¨klerin indisledi˘gi listelere posting list denir. Yani bu ara¸stırma kapsamında, sosyal a˘g alanındaki posting list’lerin kom¸suluk listesinden veri yapısı olarak bir farkı yoktur. B¨oylece, bir ters dizinin veya c¸izge dizininin sonu¸c listesi ele alındı˘gında bu listeler kar¸sıla¸stırılabilir. Ba¸ska bir deyi¸sle, gerc¸ekle¸stirilmi¸s olan i¸sle¸cler iki dizinin sonuc¸ listesini fark g¨ozetmeksizin i¸sleyebilir.
Ters dizinlerin i¸slec¸lerde kullanılabilmesi ic¸in term i¸sleci karakter dizilerini de parametre olarak alabilecek ¸sekilde gu¨ncellenmi¸stir.
Typeahead arama yapılabilmesini sa˘glamak ic¸in, indisleme ¸seması ilk karakterden ba¸slayarak ilerlemektedir. O¨ rne˘gin, ismi ”Carl” olan bir kullanıcı ic¸in, ”C”, ”Ca”, ”Car” ve ”Carl” ¸seklinde farklı indisler u¨retilmi¸stir. Bu sayede, ilk karakterden ba¸slanarak ”C” veya ”Ca” dizgilerinin indisinde ”Carl” ismindeki du¨˘gu¨mlere eri¸silebilir. Term i¸slecinin karakter dizisi parametresinin sonundaki ”*” karakteri ise yapılacak aramanın typeahead araması oldu˘gunu belirtmektedir.
C¸o¨zu¨m Yakla¸sımına Dair O¨ nemli Hususlar Gerc¸ekle¸stirilen sosyal c¸izge arama motorunda sistemin etkili ve etkin i¸sleyi¸si ic¸in bazı hususların dikkate alınması gerekmektedir. Bu hususlar a¸sa˘gıda verilmektedir: – Veriyi Sıralı Tutma. – I˙¸sle¸clerin Yerellik Gereksinimi. – I˙¸sle¸clerin Birle¸sme O¨ zelli˘gi. – Typeahead ve Standart Aramanın Sonuc¸larını Ayırma.
Her birinin ele alınıp gerc¸ekle¸stiriminde bazı ¨odu¨nle¸simler g¨oru¨lmu¨¸s ve bu o¨du¨nle¸simlere ili¸skin karar verilmi¸stir.
Sistemde kom¸suluk listesinde tutulan veriler sıralıdır. Tu¨m sosyal c¸izge verisine ait kom¸suluk listesi da˘gıtılarak i¸slenmektedir. Bu da˘gıtım esnasında liste belli b¨olu¨mlerinden kırpılmaktadır ve bu kırpma sonucunda da˘gıtılan par¸caların yine sıralı tutulması ¨onem arz etmektedir. Sistemimizdeki temel term i¸sleci i¸sletildig˘inde kom¸suluk listesi do¨nmektedir. Gereksinim duyulan di˘ger sorguları kar¸sılamak u¨zere Spark’ın intersect ve union gibi hazır fonksiyonları kullanılmak istendig˘inde kom¸suluk listelerinin eleman seviyesinde da˘gıtılması gerekmektedir ancak eleman seviyesinde yapılan da˘gıtımda her i¸slem sonrası Spark’ta elemanlar karı¸stırılabilece˘ginden mevcut sıranın kaybedilmesi sorunu ortaya c¸ıkmaktadır. Her i¸slemden sonra sıralama yapılması bu¨tu¨n da˘gıtık sistem u¨zerinde veri transferini yog˘unla¸stırır ve bu sıralama i¸slemi da˘gıtık sistemlerde en ¸cok kar¸sıla¸sılan darbog˘azlardan biridir. Dolayısıyla kom¸suluk listeleri seviyesinde da˘gıtım yapılmalıdır ve bu sayede kendi i¸clerinde sıralı olan listelerin yine sıralı bir ¸sekilde birle¸stirilmesi etkin olarak tamamlanabilmektedir. Bu tasarıma uygun olarak Spark’ın intersect ve union i¸sle¸clerinin kullanımı yerine bu i¸slec¸ler bizzat kodlanmı¸stır.
I˙¸sle¸clerin c¸og˘u hesaplamanın do˘gru yapılabilmesi ic¸in girdi listelerinin aynı makine u¨zerinde tutulmasına gereksinim duymaktadır. O¨ rne˘gin a¸sa˘gıdaki sorgu incelendig˘inde;
5 ve 6 ID’li kullanıcıların arkada¸s listelerinin kesi¸sim ku¨mesinin bulunabilmesi ic¸in sistem u¨zerinde dag˘ıtılmı¸s olan bu iki listenin aynı makine u¨zerinde bulunması gerekmektedir. Aksi halde sonuc¸ listesi do˘gru olmayacaktır. Bu nedenle and, or, weak-and ve strong-or i¸sle¸cleri c¸alı¸stırılmadan ¨once bu¨tu¨n kom¸suluk listelerinin aynı makinede birle¸stirilmesi bir c¸o¨zu¨m olabilir ancak bo¨yle bir yakla¸sım tek ve belki de uzun bir listenin tek bir makine u¨zerinde toplanması durumunu ortaya c¸ıkarır ve bu durum bundan sonra liste u¨zerinde yapılacak olan i¸slemlerin paralellik ¨ozelli˘gini kaybetmesine neden olur. Bu problemin a¸sılması ic¸in yerellik ihtiyacı olan i¸sle¸cler a¸sa˘gıdaki adımlar izlenerek c¸alı¸stırılmaktadır: – Parametre i¸slec¸lerinin sonuc¸ları aynı makine u¨zerinde toplanır, sonuc¸ hesaplanır ve e˘ger gerekli ise kırpma i¸slemi uygulanır. Bu a¸sama ile sonucun ne olması gerekti˘gi ¨og˘renilmi¸s olur. – Parametre i¸slec¸lerinin sonuc¸ları makine bazlı olarak birle¸stirilir ve ilk a¸samadan o¨g˘renilmi¸s olan sonuc¸ listesi bunlara katılır. Bu a¸samanın amacı da˘gıtıklıg˘ı sa˘glamaktır. – Son olarak, elde edilen birle¸stirilmi¸s liste ve ¨o˘grenilmi¸s sonuc¸ listesi kullanılarak birle¸stirilmi¸s listedeki ¨o˘grenilmi¸s sonuc¸ listesinde bulunmayan elemanlar elimine edilir. Bu sayede hem hesaplama do˘gru yapılmı¸s hem de dag˘ıtık bir sonuc¸ elde edilmi¸s olur.
A¸sa˘gıda verilen ¨ornekte 5 ve 6 ID’li kullanıcıların arkada¸sları P1, P2, P3 parc¸alarına dag˘ıtılmı¸stır ve bu kullanıcıların ortak arkada¸slarının sistematik bir ¸sekilde nasıl hesaplandıg˘ı go¨sterilmi¸stir.
Verilen ¨ornekte kırpma limiti 3 olarak kabul edilmi¸stir ve sonuc¸ listesinin 0, 35, 57 olması gerekmektedir.
P1 → [0, 35, 86, 96] P2 → [10, 57, 66, 94]
P3 → [75, 76, 97] (term friend:6)
P 1 → [
P 3 → [
Her iki term sonu¸c listesi par¸calar u¨zerinde birle¸stirilir ve aynı parc¸a u¨zerinde toplanır.
(term friend:5)
(term friend:6)
P1 → [0, 10, 35, 57, 66, 75, 76, 86, 94, 96, 97] P1 → [
P1 → [0, 35, 57]
Elde edilmi¸s olan liste sonuc¸ olması gereken fakat da˘gıtık olmayan ¨o˘grenilmi¸s listedir. Daha sonra ba¸slangıc¸ a¸saması’ndaki term’ler parc¸a seviyesinde birle¸stirilir yani aynı parc¸ada olan listeler birle¸sirler.
P1 → [
P3 → [
P1 → [
P3 → [
P1 → [0, 35, 57] P2 → [0, 35, 57] P3 → [0, 35, 57]
Son olarak birle¸stirilmi¸s olan listelerde ¨o˘grenilmi¸s listede olmayan sonuc¸lar elimine edilir.
P1 → [0, 35, 57]
P2 → [0, 57]
P3 → [35]
Sonu¸c olarak dog˘ru hesaplanmı¸s da˘gıtık bir sonuc¸ elde edilmi¸s olur. Sonuc¸ listesi tekrarlı elemanlar i¸cerebilir fakat eg˘er bu sonuc¸ a¸saması daha sonraki ba¸ska bir i¸slece parametre ise o i¸slecin hesaplanmasında bir soruna yol ac¸maz, e˘ger de˘gil ise sonuc¸ d¨ondu¨ru¨lu¨rken tekrarlı elemanlar elimine edilir.
And ve or i¸sle¸cleri birle¸sme ¨ozelli˘gi g¨osterir. Yani a¸sa˘gıda verilen iki sorgu birbirleri ile e¸sdeg˘erdir: – ( and ( f r i e n d : 5 ) ( f r i e n d : 6 ) ( f r i e n d : 1 2 ) ) – ( and ( f r i e n d : 5 ) ( and ( f r i e n d : 6 ) ( f r i e n d : 1 2 ) ) )
Bu ¨ozellik kullanılarak and ve or i¸sle¸cleri n tane i¸slenenle ¸calı¸sacak ¸sekilde gerc¸ekle¸stirilebilir. Buna kar¸sın weak-and ve strong-or i¸sle¸cleri birle¸sme ¨ozellig˘i go¨stermez. Dolayısıyla a¸sa˘gıda verilen iki sorgu birbirine e¸sit de˘gildir: – ( weak−and ( f r i e n d : 5 : opt−c o u n t 1 ) ( f r i e n d : 6 : opt−w e i g h t 0 . 1 ) ( f r i e n d : 1 2 ) ) – ( weak−and ( f r i e n d : 5 : opt−c o u n t 1 ) ( weak−and ( f r i e n d : 6 : opt−w e i g h t 0 . 1 ) ( f r i e n d : 1 2 ) ) )
Bu sebeple, ¸calı¸smada weak-and ve strong-or i¸sle¸cleri, sadece 2 i¸slenen ile c¸alı¸sabilecek ¸sekilde gerc¸ekle¸stirilmi¸stir. Bunun yanı sıra, bu i¸sle¸cler Spark’ın cogroup fonksiyonu kullanılarak kodlanmı¸stır ve bu fonksiyon 5 i¸slenene kadar destek verir. Gerekli deg˘i¸siklikler ile i¸sle¸clerin 5 i¸slenene kadar ¸calı¸sması mu¨mku¨ndu¨r.
Sistem typeahead ve standart olmak u¨zere iki tip aramayı desteklemektedir. term i¸slecine parametre olarak verilen karakter dizisinin * (yıldız i¸sareti) ile bitmesi durumunda typeahead arama sorgusu ifade edilmektedir: ( term ” C a r l ” ) ( term ” C a r l ∗ ” )
Mevcut problemi aktarmak ic¸in ¨ornek bir karakter dizisi ele alınabilir. O¨ rne˘gin ic¸inde ”Carl” karakter dizisini barındıran bir du¨g˘u¨m ic¸in ters dizin yapılandırılırken du¨˘gu¨m ”C”, ”Ca”, ”Car” ve ”Carl” karakter dizileri ile indislendi˘gi ic¸in standart ve typeahead bir aramanın farkı ayırt edilemez. O¨ rne˘gin, ”Carl” karakter dizisinin aranması sonucu elde edilen Hit listesindeki Hit’lerin carl s¨ozcu¨g˘u¨ne birebir e¸sit mi yoksa ”Carl” karakter dizisi ile ba¸slayan bir s¨ozcu¨k mu¨ (”Carlos”) oldu˘gu bilinemez:
Carl → (Hit1, Hit2, Hit3, Hit4)
Probleme c¸¨ozu¨m olarak, sec¸meli HitData bayt dizini kullanılarak, eg˘er listedeki herhangi bir Hit s¨ozcu¨k ile tamamen e¸sle¸siyorsa, dizinin ilk elemanına 1, ya da sadece, ilgili Hit s¨ozcu¨k ile ba¸slıyorsa 0 atanır. B¨oylece, eg˘er sorgu typeahead ise indisteki bu¨tu¨n liste sonuc¸ olarak do¨ndu¨ru¨lu¨r. Aksi takdirde, standart bir arama, listenin bayt dizini 1 ile ba¸slayan sonuc¸larını getirir.
Unicorn di˘ger arama motorlarından farklı olarak doku¨man tabanlı arama yapmak yerine sosyal ag˘da yer alan varlıklar, bu varlıklara ili¸skin bilgiler ve bu varlıkların ili¸skili oldukları dig˘er varlıklar altyapısı u¨zerinde arama ger¸cekle¸stirmektedir.
Bu kapsamda, benzer bir ¸calı¸sma olarak Aardvark[
Bu sosyal ¸cizge veri yapısı ele alındıg˘ında, bir arama motoru olmamasına ra˘gmen Sparql sorgu dili benzer bir ¸calı¸sma olarak de˘gerlendirilebilir. Sparql sorgu dili, RDF c¸izge veri ku¨meleri ic¸in tasarlanmıstir. Unicorn’a benzer olarak anlambilimsel farklılıkları g¨ozeterek, RDF veri ku¨melerindeki veriye eri¸smeyi sa˘glar. Fakat iki sistem arasındaki fark RDF verisindeki ili¸skilerin object-predicatesubject u¨¸clu¨’leri (triplet) kullanılarak, Unicorn altyapısında ise daha ¨once bahsedildig˘i gibi kom¸suluk listeleri aracılıg˘ıyla, sıralı bir ¸sekilde g¨osterilmesidir.
Gerc¸ekle¸stirilen c¸alı¸sma, sosyal a˘glar u¨zerinde arama yapmak u¨zere ¨ozelle¸smi¸stir. Bu ¨ozelle¸smeyi, klasik bilgi elde etme sistemlerinde veya arama motorlarında kullanılan ters dizin yapısı ile anlambilimsel c¸izgeler u¨zerinde tanımlanan sorgulama dili ve motorlarını entegre etmesi ile sa˘glamı¸stır. Bu entegrasyonda veri yapısı olarak kom¸suluk listelerinin kullanımı ve liste veri yapısına c¸ok uygun fonksiyonel programlama i¸slec¸lerinin uyarlanması genel ve etkin bir yapı kurulmasını sa˘glamı¸stır.
Bu c¸alı¸sma kapsamında Unicorn c¸izge arama motorunun temel bile¸senleri analiz edilip ger¸cekle¸stirilmi¸stir.
C¸alı¸smanın temel katkıları ¸su ¸sekilde ¨ozetlenebilir: – Standart bilgi elde etme kavramlarının sosyal a˘glar alanına uygulanması konusunda bilgi birikimi olu¸sturulması. – Karma¸sık c¸izge tabanlı bir arama motorunun tasarımındaki hususlar ve bu hususlar kapsamındaki o¨du¨nle¸simleri de dikkate alarak bir c¸o¨zu¨m u¨retilmesi. – Sistemdeki i¸slec¸lerin Spark u¨zerinde da˘gıtık ve paralel bir ¸sekilde hesaplanabilmesinin sa˘glanması.
Kom¸suluk listesinde sıralama ¨ol¸cu¨tu¨ olarak PageRank de˘gerinin kullanılması, i¸sle¸cler ic¸in Composite Design Pattern’in kullanılması, i¸slec¸ algoritmalarının Spark ortamına uyarlanması, Typeahead arama ¨ozellig˘inin eklenmesi yukarıda listelenen katkılara eklenti olarak de˘gerlendirilebilecek c¸o¨zu¨me dair ¨ozel niteliklerdir.
Bu ¸calı¸smada Unicorn’un c¸ekirdek yapısı Spark u¨zerinde yakla¸sık olarak 800 kod satırı ile ger¸cekle¸stirilmi¸stir. Geli¸stirilen yazılımın etkinli˘ginin i¸sle¸cler u¨zerinde yapılacak kapsamlı performans ¨ol¸cu¨mleri ile test edilmesi uygun olacaktır. Bu sayede paralel ve dag˘ıtık bir yapıda sistemin performansı de˘gerlendirilmi¸s olacaktır.
Unicorn gibi bu¨yu¨k ¨olc¸ekli c¸izge tabanlı bir arama motorunun gerc¸ek anlamda
yapılandırılması i¸cin ¸c¨ozu¨me a¸sa˘gıdaki eklentilerin dahil edilmesi de faydalı
olacaktır:
– Bellek kullanımını verimli hale getirmek ic¸in, ters dizinlere ve kom¸suluk
listelerine sıkı¸stırma algoritmaları uygulanması.
– Arama yapan kullanıcıya g¨ore sıralama (ranking) yapılması. Arama yapan
kullanıcıyla ortak veriye sahip olan Hit’lerin sıra de˘gerleri orantılı olarak
arttırılabilir. O¨ rneg˘in, arama yapan kullanıcı ”X” u¨niversitesinden mezun ise
kom¸suluk listelerinde bu u¨niversiteden mezun olmu¸s Hit’lerin sıra de˘gerleri
arttırılabilir. Zira sosyal a˘glarda ortak altgruplara aidiyetin ki¸silerin ili¸skilendirmesinde
faydalı oldu˘gu go¨ru¨lmu¨¸stu¨r [
I˙nternet ve sosyal ag˘lar hala kullanıcı sayılarını arttırmakta ve bu¨yu¨k veriler olu¸smaktadır. Yakın zamanda, ba˘glantılı bu¨yu¨k veri u¨zerinde arama yapma probleminin sadece Facebook’un de˘gil, di˘ger orta ¨ol¸cekli pek c¸ok kurulu¸sun ortak sorunu haline gelmesi beklenmektedir. Dolayısıyla bu c¸alı¸smanın yakla¸sımı ve tartı¸stı˘gı kavramlar, yeni yapılandırılması planlanan sistemlere uygulanabilir. Ayrıca, c¸izgenin ger¸cekle¸stirimi genel (generic) oldug˘u ic¸in, gerekli du¨g˘u¨m ve kenar tipleri tanımlanıp gereksinim duyulan alternatif sıralama stratejileri geli¸stirilirse sosyal ¸cizge arama motoru herhangi bir alana (DNA veritabanları) uygulanabilir.