=Paper=
{{Paper
|id=Vol-1297/234-242_paper-34
|storemode=property
|title=О некоторых проблемах анализа социальных сетей
(On Several Social Network Analysis Problems)
|pdfUrl=https://ceur-ws.org/Vol-1297/234-242_paper-34.pdf
|volume=Vol-1297
|dblpUrl=https://dblp.org/rec/conf/rcdl/ChernishevSSS14
}}
==О некоторых проблемах анализа социальных сетей
(On Several Social Network Analysis Problems)
==
https://ceur-ws.org/Vol-1297/234-242_paper-34.pdf
On Several Social Network Analysis Problems
© George Chernishev © Vsevolod Sevostyanov © Kirill Smirnov
Saint-Petersburg University, Russia
chernishev@gmail.com vsevost@gmail.com kirill.k.smirnov@math.spbu.ru
© Ilya Shkuratov
Saint-Petersburg University, Russia
shkuratov.ilya@gmail.com
Abstract • The participation is allowed to both graduate and
undergraduate students, without any restriction on
In this paper we describe our approach to sev- a number of attempts.
eral problems offered at the ACM SIGMOD Pro-
gramming Contest 2014. These problems belong While this contest is not so well known as the ICPC, it
to the area of a social network analysis and in- is nevertheless popular. For example, last year there were
volve several types of queries to a social graph. more than 100 registered teams. The contest is relatively
The considered graph is modeled by the standard young — it runs for 6th time this year.
SNB benchmark. We briefly introduce this bench- In this paper we also describe the contest: the rules,
mark, the contest and the problems. Next, we de- the task, its timeline and required qualifications. More-
scribe our contribution, which is the following: over, we present our experiences and provide a solution of
the algorithms for evaluation of these queries and the team “GenericPeople” (Ilya Shkuratov and Vsevolod
their efficient implementation. Furthermore, we Sevostyanov), which was ranked1 17 out of 33 teams on
present parallelization techniques for these algo- the preliminary (public) tests. While our approach is not
rithms and describe overall architecture of our the best, it still has merit:
solution. • our solution can serve as an example demonstrating
the required qualifications and which may help to
assess the required effort and work intensity. These
1 Introduction and Related Work factors may be of interest for a person who is think-
ing about the participation;
In this paper we study several problems offered at the
ACM SIGMOD Programming Contest 2014 [1], a yearly • the solution successfully passed through all avail-
programming contest focused on a data management top- able tests (datasets of three different sizes) within
ics. the time limits specified by the contest organizers
This contest has a number of features, which distin- (5 and 10 minutes);
guish it from a well-known ICPC series:
• the proposed algorithms passed all correctness tests;
• Participants are offered some science-intensive task,
• parallelization techniques of these algorithms may
which is usually an unsolved problem of current
be of interest;
importance.
• the number reported in the leaderboard is the sum
• The contest runs for several months and no on-site
over all query types, at the present time we can say
participation is required.
nothing regarding their individual performance;
• Topic specificity — the clear data management fo-
• at last, the number was reported for three datasets;
cus is present. For example, contests of previous
the proposed algorithms may behave differently (bet-
years involved construction of distributed query pro-
ter or worse) on another dataset.
cessing engine (2010), multidimensional index (2012)
or document stream filtering system (2013). Thus, we deem current study as worthy to be pre-
sented and of some interest for the reader. Another mo-
Proceedings of the 16th All-Russian Conference tivation for this paper is the concise presentation of the
”Digital Libraries: Advanced Methods and
Technologies, Digital Collections” – RCDL-2014, 1 http://www.cs.albany.edu/~sigmod14contest/leaders.
Dubna, Russia, October 13-16, 2014. html, last accessed 02/05/2014.
234
solution for the contest problem, which is usually lack- The goal was to develop a program which computes
ing. After the contest all what is left are the posters of the the results as fast as possible. The contestants had not
top five performing teams without detailed explanation (it only to devise the algorithms for efficient query process-
is given orally at the conference). Also, these posters are ing on a large graph, but also to parallelize them. This is a
(or at least were in the past years) not going into the con- must, given the fact that the evaluation of the resulting im-
ference proceedings and are kept on a website, which may plementation was performed on a server-class equipment
disappear. Moreover, we present our experiences and de- (8 cores).
scribe (at least partially) the way we went through in order Another important aspect was the order of compu-
to produce a working solution. It is impossible to pass on tation for each sub-query. The contestants had to bear
all these aspects via poster. in mind the size of intermediate results and the memory
This year contest was dedicated to a social network bound. In other words, the contestants had to perform the
analysis topic. Social network is essentially a graph, whose work of a query optimizer: gather needed statistics, assess
vertices represent users and edges denote relations be- selectivities and develop an optimal processing strategy
tween them. An example of such relation may be “know for each query type. Also, given the hardware multi-core
each other”, “follow” and so on. Additionally extra infor- capability, efficient inter-query type orders are also of in-
mation like a place of work or study, geographical infor- terest.
mation, various tags, images, likes etc. is known. The contribution of this paper is the following:
In the past years massive amounts of such information
• The description of the ACM SIGMOD Program-
were made available for analysis, forming a strong incen-
ming Contest 2014 and its task;
tive for both academy and industry to come with means
for its efficient storage and processing. Social data play a • The contest from the participant’s point of view:
significant role in the whole “Big Data” movement. our experiences;
A lot of analysis tools employ the MapReduce [6] pro-
gramming model. Industrial examples of such systems • The algorithms to handle the problems offered at
are PIG (Yahoo) [13], SCOPE (Microsoft) [4], Hive (Face- the contest;
book) [19], Dremel (Google) [14]. Academic examples • A parallelization techniques for each of these algo-
are Starfish [9], HadoopDB [3] and many others2 . An al- rithms;
ternative (which can be considered a poor man’s solution)
sometimes employed in production environment, is to use • A general system architecture: subquery compu-
scripts written in scripting language like Python to com- tation orders, inter-query type orders and chunk-
mence the analysis. A data scientist has to analyze the based data loading.
problem and implement all necessary algorithms manu- Now, we are going to describe our experience. The
ally. While it may not favor the rapid development, it SNB description and its data schema is presented in the
may allow to achieve a more efficient processing. Natu- appendix section. Detailed description of our approach
rally, this approach is more flexible than using a standard and data statistics can be found in the report [5].
tool and allows a fine-tuning of algorithms. However, it
requires extensive technical expertise: knowledge of al-
gorithms and data structures, the understanding of the data 2 Contest description and experiences
processing and so on. The tasks of the contest are repre-
sentative examples of this “manual” approach and can be Let’s describe this year contest from the participants’ point
considered as a training for a data scientist. of view. We have already briefly described the contest
Another aspect of the contest task is the graph anal- and its specifics in the introduction section. You can find
ysis component. Graph analysis is a mature area of re- detailed information regarding the ACM SIGMOD Pro-
search which studies the efficient storage and processing gramming Contest series in the reference [18].
of graph data. There are several graph database man- Our research group is a frequent participant of this
agement systems (a special type of DBMS) and graph contest; we had achieved good results twice in the past:
programming frameworks. These DBMS feature special in the 20103 (team “spbu”) and 20134 (team “Rota For-
query languages, query processing algorithms and data tunae”) year. Both times our teams achieved 3rd place in
storage. the final ranking.
Some examples of the graph DBMS are Neo4j [12],
InfiniteGraph [10] and the framework examples are Apache 2.1 General information
Giraph [2], Signal/Collect [17]. It is necessary to mention This year contest followed the general scheme described
that two latter systems also follow the MapReduce model. in the reference [18]. However, there were several notable
The contestants were given the task which consists of divergences:
the datasets and four types of queries. The social graph
was generated using the SNB [16] tool. 3 http://dbweb.enst.fr/events/sigmod10contest/
results/#winner, last accessed 22/07/2014.
2 A list can be found in http://dl.acm.org/citation.cfm?id= 4 http://sigmod.kaust.edu.sa/finalists.html, last ac-
1454166, last accessed 22/07/2014. cessed 22/07/2014.
235
1. The contest started noticeable later compared to pre- In the overall the contest run for two and a half months.
vious years; Also you can see that several datasets were progressively
added to the evaluation pool. These datasets were pro-
2. There were no 2nd round, unlike early years. This gressively disclosed by the organizers as the performance
change happened in 2013; of submissions improved. This is a rather new model
3. The absence of the dedicated correctness testing phase of evaluation (appeared in 2013 contest) and it was em-
during the evaluation (it was performed concurrently ployed in the following way. As soon as the several sub-
with the performance evaluation); missions were achieving some performance level, where
it was hard to discern their quality due to inaccurate mea-
4. There was a series of datasets which were progres- surements (thread scheduling effects, for example), a new,
sively disclosed by the organizers, as the perfor- larger dataset was added.
mance of the submissions improved;
2.2 Communication with the contest organizers
5. The task did not explicitly required parallelization
or concurrency support, but instead, implied it. It Information about the order and rules of the contest were
was possible to submit purely sequential implemen- provided on a special web page [1], which was the main
tation; mean of communication between the organizers and the
contestants. It also describes test data sets, the task and an
6. It was possible to submit only the executable, with-
evaluation environment. Later opportunities to register a
out source code during the preliminary evaluation.
team and submit solutions were added.
The final evaluation required source code and this
The organizers also created a Google Group in order
led to some compatibility difficulties;
to discuss any technical issues (e.g. code page problems)
7. Contestants were allowed to choose programming and to provide additional information that might be of in-
languages other than C++. terest to all of the contestants: test data-sets publication
dates, disk space availability, size of data set for the final
The provided task was a science-oriented problem re- evaluation and so on.
lated to social network analysis. The problem was to ex-
ecute a number of queries to a graph representing some 2.3 Required skills and our experiences
social network. The goal was to produce a correct answer
and minimize the overall processing time. The graph and Since the organizers of the contest considers Linux as its
queries are fully described in the next section. target platform, we decided to use C++ programming lan-
Below you can see the timeline of the contest. guage as it looks to us an highly-optimizable one. Those
who want to take part in the contest are advised to learn
• January 25, 2014 — Contest announced. Linux development utilities such as gcc, make, valgrind
(especially callgrind might be useful), gdb, etc. Also two
• February 1, 2014 — Detailed specification of the bash scripts were required: one should build the solution
requirements and test data available. and the other — run it with certain parameters.
• February 16, 2014 — A medium data set (10k peo- You also may encounter restriction on size of submit-
ple) with query workload and answers are available ted solution. It was 8 MB this year, thereby it was helpful
on the Task page. New query workload and an- for us to learn a couple of gcc flags. The first one is -s. It
swers for the small data set (1k people) are avail- removes unneeded symbols from an executable, thus re-
able on the Task page. ducing its size without the loss of performance. The sec-
ond flag may be useful, if you use external libraries: -MM
• March 1, 2014 — Team registration begins. Leader- instructs the compiler to generate source files dependen-
board available. cies. This helped us to familiarize with boost headers de-
pendencies, strip boost from unneeded header files and
• March 11, 2014 — Workloads on a medium data further reduce submitted archive size.
set (10k people) have been added to the evaluation Understanding compiler optimization methods may be
system. of use as well. It allowed us to cope with the gcc optimizer
• March 17, 2014 — Workloads on a large data set bug, namely incorrect copy propagation after global com-
(100k people) have been added to the evaluation mon subexpression elimination pass. It leads to usage of
system. the original pointer to the buffer instead of its copy, which
cause segmentation fault on an attempt to free this buffer.
• April 15, 2014 — Final submission deadline. The workaround is to add a dummy use of the original
pointer after working with the buffer.
• May 15, 2014 — Finalists announcement. Another important skill is an ability to find necessary
• June 22-27, 2014 — Conference: announcement of information on the subjects of the competition, i.e. the
the winner and the poster presentations. ability to work with digital libraries. Usually the task of
236
the competition (or one of the tasks) is an unsolved sci- (a) have that interest (see tag,
entific problem. Thus one may find useful information person_hasInterest_tag);
about methods have been tried or perspective approaches. (b) were born on d or later;
These gave us several hints for the given task.
(c) know each other (see person_knows_person,
which presents undirected friendships between
2.4 Tools
persons; a friendship relationship between per-
Aside from the usual requirements this year contest posed sons x and y is represented by pairs x|y and
an additional one: knowledge of some scripting language y|x).
or a tool for data analysis. This language can be used for
3. Query Type 3 (Socialization Suggestion). Given
data mining: to detect hidden dependencies in the source
an integer k, an integer maximum hop count h, and
data and to collect necessary statistics. We used Python
a string place name p, find the top-k similar pairs
programming language; other examples include R and Oc-
of persons based on the number of common interest
tave tools.
tags (see person_hasInterest_tag). For each of the
k pairs mentioned above, the two persons must be
2.5 Data located in p (see person_isLocatedIn_place, place,
The schema for the data used in the task formulation is and place_isPartOf_place) or study or work at or-
presented on Figure 3. Data were stored as a set of CSV ganizations in p (see
files. It is worthy to mention that not all of the files were person_studyAt_organization,
needed for the query processing. Also, organizers had person_workAt_organization,
provided data only for two datasets — the one containing organisation_isLocatedIn_place, place, and
thousand and the one containing ten thousand of persons. place_isPartOf_place). Furthermore, these two per-
These datasets are sufficient for the debug purposes, but sons must be no more than h hops away from each
they are not enough to tune algorithms for the final evalu- other in the graph induced by persons and
ation, which involved a graph of million of persons. The person_knows_person.
benchmark generation parameters were kept in secret and
4. Query Type 4 (Most Central People). Given an
it was impossible to generate that graph by ourselves.
integer k and a string tag name t, find the k persons
who have the highest closeness centrality values in
3 Problems the graph induced by persons who:
The contest offered [1] the following problems (we fully (a) are members of forums that have tag name t
provide them here for the better understanding of the reader (see tag, forum_hasTag_tag,
and in case of the original website outage): and forum_hasMember_person);
(b) know each other (see person_knows_person,
1. Query Type 1 (Shortest Distance Over Frequent
which presents undirected friendships between
Communication Paths).
persons; a friendship relationship between per-
Given two integer person ids p1 and p2, and an- sons x and y is represented by pairs x|y and
other integer x, find the minimum number of hops y|x).
between p1 and p2 in the graph induced by persons
who: Here, the closeness centrality of a person p is:
(a) have made more than x comments in reply to (r(p) − 1) · (r(p) − 1)
,
each other’s comments (see (n − 1) · s(p)
comment_hasCreator_person and
comment_replyOf_comment); where r(p) is the number of vertices reachable from
(b) know each other (see person_knows_person, p (inclusive), s(p) is the sum of geodesic distances
which presents undirected friendships between to all other reachable persons from p, and n is the
persons; a friendship relationship between per- number of vertices in the induced graph. When ei-
sons x and y is represented by pairs x|y and ther multiplicand of the divisor is 0, the centrality
y|x). is 0.
2. Query Type 2 (Interests with Large Communi-
ties). 4 Algorithms
Given an integer k and a birthday d, find the k in- In this section we describe algorithms for the tasks of the
terest tags with the largest range, where the range contest. Due to the space constraints they are presented
of an interest tag is defined as the size of the largest in a brief, a detailed version featuring algorithm listings
connected component in the graph induced by per- can be found in the report [5].
sons who:
237
In the rest of this paper we refer to the graph induced approach may be beneficial, if used differently. The idea
by “know each other” relation as graph, and to the breadth- is to produce a decomposition of the whole time interval
first search of that graph as BFS. This graph is used in into disjoint several time slices. During the query pro-
every query type and BFS (as we show further) plays the cessing we can use the projection corresponding to an in-
key role in all of them. Thus, a shorthand notation would terval d, specified by the query. These projections are
be useful. constructed during the preprocessing phase. Thus, we can
avoid some excessive comparisons during the query pro-
4.1 Query Type 1 (Shortest Distance Over Frequent cessing phase.
Communication Paths) Thereby, the estimation of the connected component
size for a single tag is essentially a BFS, performed on a
4.1.1 Algorithm description graph whose time slice conforms to the date specified by
An obvious strategy for evaluation of such query would the query. This algorithm can be easily parallelized. For
be the following: example, one can divide tag set between threads equally
and then construct a final result by joining results for the
1. Run BFS from person p1 to person p2 and return individual tags.
hops count;
2. During the BFS traversal one needs to check the 4.3 Query Type 3 (Socialization Suggestion)
replies condition. For each edge, considered on a 4.3.1 Algorithm description.
given BFS step, one has to calculate the number of
mutual replies for the corresponding persons. If it The common sense may provide the following idea of the
is less than k, then the transition is not possible — straightforward evaluation:
the edge does not exist.
1. for each vertex v in the graph perform BFS while
This “naive” approach needs no preparation and can keeping in mind the given hops count h;
be ran just after the graph construction. For each pair of
2. upon completion BFS returns the list of reached
adjacent persons it is necessary to calculate the number of
people rp;
replies and this may take some time. Thus, the described
BFS has the complexity O(m · n · (|V | + |E|)) where n 3. for v and each person vr from rp check information
denotes a cardinality of “comment is reply of comment” about their work places, study places and location
relation and m — cardinality of “comment has creator for correlation with p;
person”.
Therefore, we propose a pretreatment phase that will 4. if one of the places where both v and vr are in-
compute number of replies once, which effectively elim- volved is p or its subplace, then calculate the num-
inates the repeated calculations. Our goal is to find per- ber of common interests ci;
sons that made not less than k comments replying to each
5. store (sorted by ci) the resulting pairs (v, vr );
other. For each pair of persons connected by an edge e in
the graph we will determine the number of mutual replies 6. return the top-k pairs as a result.
ke and attribute it to e. In this way, BFS on each step com-
pares two numbers: given k and pre-calculated ke . This algorithm requires examination of all the persons
returned by BFS. Since graph is a social its edge count
follows power law, therefore there are some hubs and con-
4.2 Query Type 2 (Interests with Large Communities)
nectors with large degree and many vertices with only a
In order to reduce the overhead related to connected com- few incident edges [11]. Hubs and connectors shorten the
ponent size estimation one needs to take into account re- paths between persons and thus, the size of rp may be
strictions which are specified by the query. To tackle the significant. The time complexity of this algorithm is
first restriction (the common tag requirement) we built a
“tag-person” index. It allows to search persons which are O(|V | · (|V | + |E| + |rp| · |person.places|
interested in a given tag. We employ the resulting list dur- + |person.interests|)).
ing the node traversal. It allows us to avoid visiting nodes
(persons) which are not interested in a given tag. Also we It is desirable to reduce the number of persons to ex-
avoid expenses related to probing person interest list for amine without the loss of result correctness. In order to
a given tag. do that we suggest to group persons by some of place
The second restriction which we have to take into ac- types. SNB provides three place types: city, country
count — the birthdate restriction. This restriction can be and continent. The type country seems to be a good
tackled by projecting our graph to a given time interval. choice (see [5] for the explanation).
By doing so, we avoid excessive comparisons related to Using the proposed partitioning we suggest a follow-
birthdate which take place during the query processing. ing improvement: use the type of p to determine which
In this case the comparisons are moved to the preprocess- country c to process and then perform BFS for each per-
ing phase, thus providing us no benefit. However, this son v from c bearing in mind the given hops count h. That
238
way only persons from c are stored in rp, which reduces be particularly efficient for unweighted, undirected graph
its size and allows us to reach our goal. of a large size. It can reduce the amount of computations
Described approach time complexity is for a majority of vertices or even avoid their processing
at all.
O(|persons in p|·(|V |+|E|+|rp|·|person.interests|)).
4.4 Query Type 4 (Most Central People) 5 System architecture
4.4.1 The calculation of closeness centrality metric Graph structure. Considering the graph structure we
bear in mind the following: (i) the cardinality of vertices
First of all, we should note, that our graph is an undirected
may run up to a million, (ii) BFS is crucial for the evalu-
graph, therefore r(p) can be calculated once for each con-
ation of every query type. Therefore, our approach must
nected component. Thus, the problem is how to compute
have low memory footprint and provide efficient BFS eval-
s(p).
uation. In order to satisfy these requirements we use rep-
An algorithm selection. Given the fact that our graphs
resentation similar to adjacency lists, but with arrays in-
is an undirected one and the edges are of unit weights,
stead, that is, each vertex contains a pointer to an array of
a simple BFS modification would suffice for the evalu-
adjacent vertices. It allows us to meet the memory con-
ation of s(p). For this purpose we can label each vis-
strains and avoid unnecessary comparisons in the BFS im-
ited vertex with the distance to the initial one. In this
plementation.
approach we do not increase asymptotic complexity of
Layers.Three layers may be distinguished in our im-
BFS and do not use additional memory. We would re-
plementation: (i) file loading, (ii) structure initialization
quire O(|V | + |E|) time and O(|V | + |E|) memory. This
and preparation, (iii) query evaluation.
estimation is better than estimation for many classical al-
This layered structure is rather natural to the task and
gorithms oriented for general cases of problem “minimal
allows some flexibility in the setting up the order of query
distance from one vertex to all other”. For example, Dijk-
evaluation. That is a rather important feature for the per-
stra algorithm [7] for graphs with non-negative weights,
formance improvement. The use of the first layer is to
based on Fibonacci heap [8] uses O(|V | + |E|) memory
provide the interface to chunk-based file loading. It copes
and O(|V | · log |V | + |E|) time. Moreover, our approach
with the problem of big files which can be up several gi-
is easily parallelizable: we can compute s(p) in parallel
gabytes in size. The use of the second layer is to parse
for different vertices.
loaded files and to build indexes and other structures re-
The cut-off heuristic. One can note that closeness
quired for the query evaluation. The last layer is respon-
centrality is inversely proportional to s(p) within a con-
sible for the final results formation.
nected component. Thus, we can propose a criterion for a
vertex to enter the top-k of a given connected component
which uses it’s s(p). Let’s define a threshold: 6 Experiments
Θ= max s(p) . In this paper we present some experiments illustrating the
p ∈ current_top_k
performance of our approach. Unfortunately, we could
Now, we can interrupt the computation of s(p), if the cur- not provide detailed experimental data from the contest
rent value had exceeded the threshold Θ. due to several reasons: (i) we do not have access to the
Despite the simplicity of this cut-off heuristics it dras- final benchmarks (they are not yet released to public); (ii)
tically decreased the evaluation time for the fourth query we no more have access to the hardware used for the eval-
type. Unfortunately, we do not know the number and pa- uation by the organizers (it was a server-class one); (iii)
rameters of queries of this type during the final evalua- the two largest benchmarking query sets are unavailable
tion. But the implementation of this heuristic allowed to too (we used the largest available dataset — the medium
decrease the evaluation time for more than 380 seconds dataset, containing 10k persons).
on a graph containing 100 thousand persons. The result- Thus, we had to perform experiments on our own.
ing time was 220 seconds. The hardware and software setup was the following: i7-
We also construct a special index structure for this 4930K CPU (6 cores), P9 X79WS motherboard, 4GB RAM;
type of query. More details can be found in the report [5]. Ubuntu 14.04, kernel 3.13.0-24, x86_64.
Other approaches. In the last few days of the con- The first series of experiments is presented on Fig-
test we found the solution that fits almost perfectly into ure 1. They illustrate the basic approach when we sequen-
the described problem [15]. It is developed for directed tially evaluate queries of the same type. The results show
graphs with non-negative weights and reuses the CCV of the contribution of each query type to the overall process-
a single vertex in order to estimate CCV for other vertices ing time. In this series we vary the number of threads.
and reduce the further computations. Authors also use es- Eventually we get a U-shaped graph, which shows that
timates in order to produce the cut-off of vertices which it’s not useful to employ more than four threads for the
not to get into top-k. That method could be modified to processing in this scenario. It is the result of the algo-
take into account the memory restrictions. The experi- rithm parallelization imperfection (not all algorithms use
ments described by authors show that this approach may
239
all cores all the time) and of the synchronization over- [4] Ronnie Chaiken, Bob Jenkins, Per-Åke Larson, Bill
heads. This leads us to the idea of pre-treatment phase Ramsey, Darren Shakib, Simon Weaver, and Jin-
which will allow us to balance the load. The load balanc- gren Zhou. 2008. SCOPE: easy and efficient par-
ing will be done by grouping tasks together into stages allel processing of massive data sets. Proc. VLDB
and reordering of query types. Endow. 1, 2 (August 2008), 1265–1276.
To examine our idea, we had split the query evalua-
tion into the following stages (the stages are described in [5] On Several Social Network Analysis Problems: a
the [5]): (i) Q3 evaluation and Q1 preparation part 1, (ii) Report. George Chernishev, Vsevolod Sevostyanov,
Q1 preparation part 2, Q2 preparation and Q4 preparation, Kirill Smirnov, Ilya Shkuratov. Technical re-
(iii) Q1 evaluation, (iv) Q2 evaluation, (v) Q4 evaluation. port. http://www.math.spbu.ru/user/chernishev
Tasks belonging to one stage are executed in parallel. Fig- /papers/sigmod2014contest-report.pdf
ure 2 shows the results for this kind of processing. Despite [6] Jeffrey Dean and Sanjay Ghemawat. 2008. MapRe-
that in fact we used our idea in the first two stages only, duce: simplified data processing on large clusters.
the performance boost of the evaluation with six threads is Commun. ACM 51, 1, 107–113.
about 28% (compared to the best performance from Fig-
ure 1) and 56% comparing the performance with the six [7] E. Dijkstra. 1959. A Note on Two Problems in Con-
threads. This may be considered a good result for the nexion with Graphs”, Numerische mathematik, vol.
medium dataset, which we use for testing. Efficiency of 1, no. 1, 269–271.
such task grouping is determined by the “closeness” of
the tasks executed in parallel in terms of time. The closer [8] M. L. Fredman and R. E. Tarjan. 1984. Fibonacci
times of execution, the more efficiently we use the pro- Heaps And Their Uses In Improved Network Op-
cessor. We can perform the load balancing in two ways: timization Algorithms. In Proceedings of the 25th
by varying the number of threads for one task and by vary- Annual Symposium on Foundations of Computer
ing the number of tasks. Hence we can use this approach Science, 1984 (SFCS ’84). IEEE Computer Society,
to tune performance further. However, effects of the load Washington, DC, USA, 338–346.
balancing may vary with the dataset. Taking such vari- [9] H. Herodotou, H. Lim, G. Luo, N. Borisov, L. Dong,
ation into account is rather difficult and requires a more F. Cetin, and S. Babu. Starfish: A Self-tuning Sys-
detailed study of the data structures and the algorithms tem for Big Data Analytics. In Proc. of 5th Conf. on
involved. Innovative Data Systems Research (CIDR), 2011.
[10] InfiniteGraph: The Distributed Graph Database.
7 Conclusions
Whitepaper. http://www.objectivity.com/wp-
In this paper we described the ACM SIGMOD Contest content/uploads/Objectivity_WP_IG_Distr_
2014, its tasks, timeline and our experiences. Also we Benchmark.pdf. Accessed 23/05/2014.
presented our approach to the offered problems and de- [11] LDBC SocialNet Benchmark: Data Generation.
scribed the advantages over the naive processing. We https://github.com/ldbc/ldbc_socialnet_bm
discussed algorithms as well as parallelization techniques /wiki/Data-Generation#graph-generation.
and presented the general system architecture. Its key Accessed 23/05/2014.
points are the following: query type intermixing, query
type reordering, continuous query processing and block [12] The Neo Database — A Technology Introduc-
file loading techniques. tion (20061123). http://dist.neo4j.org/neo-tech
nology-introduction.pdf. Accessed 23/05/2014.
References [13] Christopher Olston, Benjamin Reed, Utkarsh Sri-
vastava, Ravi Kumar, and Andrew Tomkins. 2008.
[1] ACM SIGMOD 2014 Programming Contest web- Pig latin: a not-so-foreign language for data pro-
site. http://www.cs.albany.edu/~sigmod14 con- cessing. In Proceedings of the 2008 ACM SIG-
test. Accessed 23/05/14. MOD international conference on Management of
[2] Apache Giraph website. https://giraph.apache. data (SIGMOD ’08). ACM, New York, NY, USA,
org/. Accessed 23/05/2014. 1099–1110.
[3] Azza Abouzeid, Kamil Bajda-Pawlikowski, Daniel [14] Sergey Melnik, Andrey Gubarev, Jing Jing Long,
Abadi, Avi Silberschatz, and Alexander Rasin. Geoffrey Romer, Shiva Shivakumar, Matt Tolton,
2009. HadoopDB: an architectural hybrid of and Theo Vassilakis. 2010. Dremel: interactive
MapReduce and DBMS technologies for analytical analysis of web-scale datasets. Proc. VLDB Endow.
workloads. Proc. VLDB Endow. 2, 1 (August 3, 1–2 (September 2010), 330–339.
2009), 922–933. [15] Paul W. Olsen, Alan G. Labouseur, Jeong-Hyon
Hwang. “Efficient Top-k Closeness Centrality
240
25 25
Query 1 Stage 1
Query 2 Stage 2
20 Query 3 20 Stage 3
Query 4 Stage 4
Stage 5
15 15
Time
Time
10 10
5 5
0 0
1 2 3 4 5 6 3 4 5 6
Thread count Thread count
Figure 1: Performance scalability (without Figure 2: Performance scalability and effects of
pre-treatment phase). query reordering (pre-treatment phase).
Search”. In Proceedings of the Data Engineering network data management tasks, a standard benchmark,
(ICDE), 2014 IEEE 30th International Conference, called Social Network Benchmark (SNB) [16] was de-
p 197-207, Chicago, IL, USA, 2014. veloped. This benchmark allows not only efficient, but
also a repeatable evaluation for a variety of scenarios: on-
[16] Social Network Benchmark (SNB) line transactions, business intelligence and graph analyt-
Task Force Progress Report ics. Authors of the benchmark tried to make it as realistic
http://www.ldbc.eu:8090/download/attachments as possible.
/4325436 /LDBC_SNB_Report_Nov2013.pdf. Covered systems. This benchmark covers several types
Accessed 23/05/14. of systems: graph DBMS and graph programming frame-
[17] Signal/Collect Documentation (website). works, RDF database systems, relational and NoSQL da-
http://uzh.github.io/signal-collect/documenta tabase systems.
tion.html. Accessed 23/05/14. Data schema. The general data schema of the bench-
mark is presented on Figure 3 (illustration taken from [16]).
[18] ACM SIGMOD Programming Contest: an It is called Social Intelligence Benchmark Data Schema.
opportunity to study distinguished aspects The schema uses UML notation to describe entities, at-
of database systems and software engineer- tributes and their relationships of different cardinalities.
ing. Kirill K. Smirnov, Georgiy A. Cherni- The schema defines the result of the benchmark’s data
shev. 2012. Компьютерные инструменты в generator. Essentially it is a set of tables linked via primary-
образовании, 6(2012), 22–25, ISSN: 2071-2340, foreign key relationships.
url:http://ipo.spb.ru/journal/index.php?article The schema defines some social network and its most
/1541/ (in Russian). characteristic features:
[19] Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, 1. users and their personal details, tags and likes;
Zheng Shao, Prasad Chakka, Suresh Anthony, Hao
Liu, Pete Wyckoff, and Raghotham Murthy. 2009. 2. relations between users (follows and knows);
Hive: a warehousing solution over a map-reduce 3. textual content: posts and comment trees.
framework. Proc. VLDB Endow. 2, 2 (August
2009), 1626–1629. Generator and its output: technical details. This
benchmark is essentially a synthetic data generator, which
is implemented using MapReduce programming model.
8 Appendix: SNB Description
The generator is dictionary-based and is capable of gen-
Let’s briefly survey the SNB benchmark which was used erating correlated values. The result of the generator is
during the contest and in the experimental section of this the set CSV files, where each file contains records of the
paper. corresponding table.
The purpose. In order to provide efficient evaluation The benchmark and the contest. The organizers
for a variety of algorithms, tools, frameworks for social of the contest used only the dataset generator, but not
241
Figure 3: Social Intelligence Benchmark Data Schema
queries. Instead, they proposed four stand-alone types of released to the public. The third one was discussed in
queries, which we described earlier. the mailing list, where some of the generator parameters
The dataset generator provided four types of graph for this dataset were disclosed. However, no queries are
workloads: small (1k vertices), medium (10k vertices), known. In this paper we use the largest available (on the
large (100k vertices) and huge (1M vertices). The last current date) dataset — the medium one for the experi-
one would be used for the final evaluation by the contest mental evaluation. All of the queries are known at the
organizers. start of the processing, contestants are not required to pro-
Unfortunately, only the first two datasets were fully cess them in a specific order.
242