## Gotta graph’em all: Pokémon and graph databases

Inspired by the Pokémon Go hype that’s been around these days, at Sparsity felt like sharing with you an application of graph technologies to catch’em all. We will show you how to use a graph database like Sparksee in conjunction with a document-oriented NoSQL database like MongoDB to find the best Pokémon for a battle depending on your opponent.

Let’s start with a little Pokémon background, although odds are that if you are reading this, you won’t need it at all.

All Pokémon creatures and their moves are assigned to a certain type [1]. From generation 1 to 6, the latter being the most recent Pokémon generation in production, there are 18 of those types. Each type has strengths and weaknesses when facing other Pokémon in battle. These can be grouped into 5 different relationships that define how effective will a creature’s defence or attack be.

→ Receives 2x damage from opponent
→ Inflicts 1/2 damage to opponent
→ Inflicts 2x damage to opponent
→ Inflicts no damage to opponent

As we are conceiving the graph as a whole, we should simplify the relationships as they are different sides of the same coin. To match the visualisation of the edge direction with the meaning of its label, we will use the “inflicts” relationship.

### Strengths and weaknesses graph:

To create the graphical representation of the graph we used a table by Sheri-B.

We created two subgraphs to simplify its visualisation –one of them highlighting the positive relationship types (edges called inflictsx2) and the other one the negative relationship types (inflictshalf and nodamage edges).

### Inflicts 1/2 and No damage subgraph:

With the graph, finding the best type match for a Pokémon battle is as simple as a neighbours query. You could use a key-value or document nosql databse like MongoDB to store a list of all gen 6 Pokémon and its types [2]. This way we could find first the type of creature we are facing and then traverse the graph, for the type with the greater strengths against the opponent. Here’s how we would code it:

If T1 is your opponent’s Pokémon type

``````
function Objects Catchemall (T1) {
//We are getting all types that inflict a X2 damage to T1
A = neighbors (T1, edge Inflictsx2, ingoing) ;
//We are getting all types to whom T1 does not inflict any damage at all
B = neighbors (T1, edge nodamage, outgoing);
AB = intersection (A,B);
if (AB != null) return AB;
else if (B != null) { return B; }
else {
//We are getting all the types to whom T1 inflicts half damage
C = neigbors (T1, edge Inflictshalf, outgoing);
CA = intersection (C, A);
if (CA != null) return CA;
else if (A != null) { return A; }
else return C;
}
```
```

*Call Catchemall for every type of your Pokémon rival (Pokémons can have more than 1 type)
* This is a pseudo-code check your language of preference at the Sparksee reference guide for the exact neighbors and interseaction operation signature.

## Example: How to fight Pikachu

To better understand the process, let’s have a look to an example where the Pokémon we have to fight is Pikachu.

Step 1:

Which type is Pikachu? Answer → Electric.

Step 2:

Call the Sparksee Catchemall function with T1 == Electric.

``````
Objects result = Catchemall (T1);
```
```

Answer → The function returns the Object type Ground because this type inflicts 2x damage to Electric and Electric attacks have no effect on Ground. Thus, this is the best option possible, our algorithm would stop at the first return.

Step 3:

Which Pokémons are of type Ground?
Answer → list of Ground Pokémon. If you have one of them, Lucky! Chances are that you will be the winner.

Graphical representation of the example.

Notes to the article:

[1] There are more variables to be taken into consideration in a battle, such as the level, the secondary type or the attacks your Pokémon learnt, but for simplicity we are considering only the type of Pokémon.

[2] Optionally you can represent Pokémons as a new type of node and add a belong edge to relate them to the type of Pokémon.

## Sparsity presenting CIGO! at Mobile World Congress 2016

Sparsity will be at this next Mobile World Congress edition that takes place in Barcelona from the 22nd to the 25th of February.

We will have a stand in the Catalonia area (Hall Congress Square CS50) presenting our new Smart Mobility platform: CIGO!.

CIGO! is a cloud platform to make mobility decisions actionable through mobile apps. CIGO! helps cities and companies make sense out of the data available improving their operational efficiency to make an impact on the mobility and ultimately in the citizen’s quality of life.

We will also be presenting the new Route Advisor and Recommender API. Built on top of Sparksee Mobile, it includes algorithms that will ease the development of any app with routing and recommendation features.

In this folder you can find more documentation about CIGO!, its use cases, Sparksee Mobile and the Route Advisor and Recommender API.

We also invite you to the talk by CEO of Sparsity Mr. Josep Lluís Larriba-Pey, who will present CIGO! and the Route Advisor and Recommender API on Wednesday 24th at 13:00 in the Catalonia booth (CS50).

If you are attending MWC 2016 don’t hesitate to come see us!

## Recap of the year and future outlook for 2016

Now that 2015 is coming to an end, it’s a good time to look back and go over what has happened in Sparsity over the year. It has been a season of new projects and challenges, but also a year to acknowledge the work done by our team in previous projects.

Thanks to the hard work and great results of the LDBC and Coherent PaaS projects, we have ranked #1 in the first Innovation Radar Report published by the European Commission. Thus, we can proudly say that Sparsity has been considered the SME with the highest innovation capacity in ICT. We also kept committed to using our knowledge and technology to bridge the gap between innovation and its social impact, having started three new projects funded by the European Union.

Sparsity is developing CIGO!, a cloud platform to ease the deployment of mobility policies towards an efficient, balanced and citizen-oriented Smart City. CIGO is funded by the frontierCities accelerator programme under the FP7. CIGO is a platform in the form of a Web App and a set of associated Mobile Apps designed to ease the implementation of mobility policies in an innovative way that benefits four key customer segments: the City Government, shops and restaurants in the city, final users and mobile apps providers.

Sparsity is also involved in the IT2Rail -“Information Technologies for Shift2Rail” project, which aims at providing a new seamless travel experience, giving access to a complete multimodal travel offer which connects the first and last mile to long distance journeys. Sparsity will be participating in the Interoperability Framework for its Semantic Query & Aggregation Engine, and with specially more stress on the Business Analytics Framework (BAF).

During the year, Sparsity has also started a new Tetracom Technology Transfer project based on the research on Query Expansion carried out by the Data Management group (DAMA) at UPC-BarcelonaTech, that will bring the state of the art research into market.

Aside of the new projects, one of the great hits of 2015 has been the release of Sparksee 5.2 with new features like the fastest and more precise community detection algorithm as part of our graph algorithm package, concurrency performance boost in read transactions, faster shortest path algorithm and added support for 64 bits processors on Android.

Over the year we have also attended interesting events and conferences such as the Mobile World Congress, Smart City Expo, Science Business Summit and Connect EU in Barcelona, the European Congress on the Future Internet in Hamburg, the SIGMOD conference and GRADES workshop in Melbourne, HiPEAC Conference in Amsterdam,
We have also successfully organised two relevant events: GraphTA and the LDBC Technical Community Meeting.

Thanks to the team, the Sparksee community and the feedback of our clients and partners, 2015 has been a great year for Sparsity. We believe that 2016 will definitely be another year of accomplishments, full of new projects and challenges and the same will to keep moving forward with knowledge, passion and dedication.

We wish you the best for the holiday season and a happy new year 2015!

## Sparsity at the Smart City Expo World Congress 2015 presenting CIGO!

Sparsity will be at this next Smart City Expo World Congress edition that takes place in Barcelona from the 17th to the 19th of November.

The Smart City Expo World Congress (SCEWC) it’s a worldwide leading event for the smart city industry, with more than 350 renowed speakers, popular side events such as the 4YFN or the BcnRail Congress, exhibition area and smart network activities. The SCEWC attracts thousands each year, making it consistently the top event for exhibitors and visitors alike.   The SCEWC seeks to give everyone involved the chance to be inspired, share experience and knowledge, strive for innovation, network and do business.

Sparsity will present our latest project called CIGO!

CIGO! is a cloud platform to ease the deployment of mobility policies towards an efficient, balanced and citizen-oriented Smart City.

CIGO! is aimed at:

• City Governments: To deploy their mobility policies through mobile apps while monitoring KPIs.
• Points of interest (POIs), shops & restaurants: To increase their exposure and awareness among citizens and tourists.
• Citizens & tourists: To discover POIs, shops, restaurants and new areas avoiding crowded & overpriced places while getting personalised routes around the city.
• Mobile Apps developers: To enrich their Apps with new content for their apps and recommendation functionalities.

Our coordinates are:

GV – P2 – Street D – Stand 44915 (Generalitat de Catalunya area)

## Sparsity involved in IT2Rail project: a step towards a new seamless multimodal travel experience

The IT2Rail -“Information Technologies for Shift2Rail” project is a first step towards the long term IP4 -“IT Solutions for Attractive Railway Services”, which aims at providing a new seamless travel experience, giving access to a complete multimodal travel offer which connects the first and last mile to long distance journeys.

The project will achieve its objectives by taking into account this concept: The traveller is placed at the heart of the solutions, accessing multimodal services like shopping, ticketing and tracking while using an open published framework providing full interoperability.

The following benefits will raise from IT2Rail:

• Impact on the economics travel services providers escosystem: By supporting full semantic interoperability of interchangeable and loosely coupled tools, data and services, within a distributed ‘web of transportation things’, multiple concurrent implementations will be developed independently by specialist suppliers and co-exist competitively.
• On time to market for innovations: By allowing an early discovery of potential technological, organisational or business process issues and reducing the risks of expensive redesign and rework.
• Enrich passenger experience: By having an integrated use case for travellers, services retailers and transport operators.

Sparsity will be participating in the Interoperability Framework for its Semantic Query & Aggregation Engine, and with specially more stress on the Business Analytics Framework (BAF). The BAF is focused on leveraging social, mobile, structured and unstructured data to obtain valuable, actionable insights that allows rail operators, product/service providers, Traveller/Transport Enterprises to make better decisions in order to increase quality of service and revenues, to better adapt their level of service to the passengers demand and to optimise their operations in order to bring and retain more people on the train-urban mobility.

Keep informed about the project here: http://www.it2rail.eu/ and via the hashtag #it2rail from Twitter.

Stay tuned for our next post about IT2Rail with more details about the Business Analytics Framework and our work.

## Help Sparsity win the first EC Innovation Radar prize

To put the spotlight on some of the brightest new ideas in European technology, the European Commission is awarding innovators agents for the first time with the Innovation Radar prize. The award recognises the most promising innovators emerging from EU funded projects in the area of information and communication technologies.

After being considered the European SME with highest innovation capacity in ICT by the EC, Sparsity is now among the 14 shortlisted companies to win the Innovation Radar prize. Taking into consideration the results of the public poll, the judges will announce the winner at the ICT 2015 event in Lisbon on the 20-22 Oct 2015.

Voting is easy: click on the links below for each language and search for Sparsity Technologies on the list.

We truly appreciate your support to make Sparsity grow, thank you very much for your help!

## Understanding Graph Structure of Wikipedia for Query Expansion

Knowledge bases are very good sources for knowledge extraction, the ability to create knowledge from structured and unstructured sources and use it to improve automatic processes as query expansion. Wikipedia, in particular, could be analyzed to see how articles and categories relate to each other and how these relationships can support a query expansion technique. In particular, the authors of this article show that the structures in the form of dense cycles with a minimum amount of categories tend to identify the most relevant information.

Let’s see a little overview on this approach. Read the complete article by Joan Guisado and Arnau Prat, presented during last GRADES 2015 in Melbourne.

Query expansion is the process of expanding a query issued by a user, introducing new terms, called expansion features, in order to improve the quality of the retrieved results. Query expansion is motivated by the assumption that the query introduced by the user is not the best to express its real intention. For example, vocabulary mismatch between queries and documents is one of the main causes of a poor precision in information retrieval systems. Poor results also arise from the topic inexperience of the users. The challenge is to properly select the best expansion features.

Wikipedia has been proven to be a good source for query expansion, but the innovation in this paper lies in the fact of considering the differences between a social network and a knowledge base by:

• Creating a ground truth consisting of those articles in Wikipedia that provide good results for each of the queries that are the baseline in the experiments.
• Analysing how the articles and categories of the ground truth are structured within the Wikipedia graph.
• Identifying cycles of articles and categories as an important structure and also trends within them. 30% of the dense cycles with minimum ratio of categories, are tagged as the best expansion features.
• Identifying challenging and open problems for graph processing technologies when it comes to exploit structures of large graphs such as Wikipedia

A quick analysis of the query graphs reveals that they are, in general, disconnected graphs composed by a moderately large connected component. This is an interesting observation as it means that, in general, the terms users introduce in a search engine are semantically related either directly or by means of extra articles or categories. This suggests that Wikipedia, contains this semantic relation encoded within its structure, and therefore, can be exploited. Also, we observe that the largest connected component is clearly dominated by categories.

If you are interested in query expansion, make sure to check our first post with the basis of this on-going research.

Also, if you are using graphs for your research don’t hesitate to request being part of our Research program where we grant free licenses of Sparksee.

## Sparsity involved in SOMATCH EU project: bringing BI to SMEs of the fashion industry

We are glad to announce that Sparsity will take part of the SOMATCH EU project under the Horizon 2020 programme. The main objective of the project is the improvement of the competitiveness of European SMEs dedicated to fashion design and Textile & Clothing (T&C) sectors by providing an IT solution that will hand over to creative designers detailed and reliable fashion trends estimations and forecasts of user acceptance for clothing designs. This will be achieved with the creation of an innovative tool for the mining and visualization of large sets of unstructured data, regarding the use and preferences of fashion products by consumers, supporting T&C companies quick reaction to the market dynamics and better adaptation of design to real consumers’ demand.

SOMATCH faces its complex and challenging deal by the combined development and application of SoA advanced image analysis technology- unexploited and innovative in clothing and fashion- combined with social network analysis.

The visualisation of the generated data will be performed from off-line statistics, generated after data processing, and by new real-time instruments for image collection and designs evaluation. They will be targeted also by the integration of the systems with new SoA mobile devices to collect information and to visualise trend interpretation. This approach will open a vast field of new approaches for the fashion designers, supporting end users involvement into the whole trend evaluation and a close interaction with them.

Sparsity’s role in the project is to provide the Social Networks Analysis to detect influential trendsetters powered by Sparksee high-performance graph database management system. Other project partners include research centres focused on image and content analysis (Technical University of Munich, UPC-Barcelonatech), software providers with expertise in the fashion industry and platform development (iDeal, Holonix), end users from SME textile industry and retail (Dena Cashmere) and fashion-related social networking and e-commerce sites owners (Weblogs, Not Just a Label).

## Sparsity is the SME with the highest innovation capacity in Europe according to the European Commission

Sparsity Technologies is the SME with the highest innovation capacity in Europe according to European Commission’s first Innovation Radar (IR) Report published last week by the Joint Research Centre. The IR report is a support initiative that focuses on the identification of high-potential innovations in the ICT FP7, CIP and H2020 EU funded projects and the key organisation in delivering these innovations to the market. The report documents the details of the IR methodology and the results of its first application.

Between May 2014 and January 2015, the Commission reviewed 279 ICT projects, equivalent to the 10.6% of ICT projects funded by the EC, which had resulted in a total of 517 innovations, delivered by 544 organisations in 291 European cities.

Sparsity has been identified as a key organisation in two innovations:  the first one, providing a new method to partition any given graph into its community structure of strongly connected components, within the Linked Data Benchmark Council (LDBC) project whose goal was to create the first comprehensive suite of open, fair and vendor-neutral benchmarks for RDF/graph databases. The second, the development of the common query engine for the different “one size” data stores optimized for particular tasks, data, and workloads, within the CoherentPaaS project whose objective is to provide a rich PaaS (Platform as a service).

Top 10 SMEs and their innovations

Barcelona, where Sparsity has its headquarters, has been identified as the largest innovation hub in ICT in Europe, hosting a total of 19 organisations that are key players in innovation and beating London and Paris which each host 17 such organisations. According to the report, Germany, Spain and the UK are the countries with the most organisations that are key players in delivering innovations.

Sparsity wants to thank all the hard work and dedication of the talented Sparsity team that during all these years has made possible this great achievement!

## Microblogging queries on graph databases

In the last edition of the GRADES Workshop co-located with SIGMOD/PODS Conference, a group of researchers from the RMIT University (Australia) presented the paper “Microblogging Queries on Graph Databases: An Introspection”. In this paper the authors shared their experience on executing a wide variety of micro-blogging queries on two popular graph databases: Neo4j and Sparksee(*). Their queries were designed to be relevant to popular applications making use of microblogging data such as from Twitter providing friend recommendations, analyzing user influence or finding co-occurrences. The queries were executed on a large real graph data set consisting of nearly 50 million nodes and 326 million edges. In this post we are going to discuss about the conclusions drawn by the researchers of the paper from the execution of 2 of the most relevant advanced queries: recommendation queries and influence queries.

## Recommendation queries

User recommendation on microblogging sites like Twitter usually involves looking at 1-step and 2-step followers and/or followees, given that it is more probable to know or share interests with the local community that the friends of your friends (or followers) create rather than with an outsider. Taking this into account the paper describes the following recommendation query:

• Q4.1 finds all the 2-step followees of a given user A, who A is not following. Such followees are recommended to A.

To implement Q4.1 Sparksee offers the neighbours operator which will return all the followers of a certain user hence all the neighbouring nodes for the edge follows for the given user. This would be a good example of the type of information to materialise at the creation phase of your database so you’ll have an index created to access to them and will result in faster retrieval queries. In this case the authors decided to avoid materialisation during the import phase to make it faster. It is always a trade-off between having a faster import/creation or better query performance that should be considered regarding each particular scenario. The result of executing Q4.1 are shown in Figure 1.

Figure 1: recommendation query (Q4.1) execution results.

Finding 2-step followees results in an explosion of nodes when 1-step followees have high out-degree forcing the systems to keep a large portion of the graph in memory. The authors explain the sudden spike in the plot for Neo4j with the fact that, the direct degree of the node in concern is much higher even though the number of rows returned are lower and they think noteworthy to mention that “Neo4j’s performance degrades with a large intermediate result in memory while Sparksee is able to take advantage of the graph already in memory observing less fluctuations with the output”.

When looking at Figure 1, one should also note the scale differences on the Y axis between the two plots, which can be misleading. The plot on the right (Sparksee) shows the average time in almost 2 orders of magnitude less than the plot on the left (Neo4j). So for example at 750k rows Sparksee’s average time is around 1.7 seconds, while Neo4j’s is around 47 seconds.

## Influence queries

Trying to discover which is the current or potential influence of a user on his or her community is useful in a wide range of situations from affiliate marketing strategies to ad targeting. Although there are plenty of models of influence propagation the authors in the paper take an intuitive road defining it as:

• Current influence: the most frequent users who mention someone and who are already followers of that user.
• Potential influence: people who are most mentioning an user without being direct followers of that user.

Both in Neo4j and Sparksee this translates to finding the users who mentioned A, and removing (or retaining) the users who are already following A. The performance results of finding influencers are shown in Figure 2:

Figure 2: influence query (Q5.2) execution results.

Like in Figure 1, the plot on the right (Sparksee) shows the average time in 2 orders of magnitude less than the plot on the left (Neo4j), which means that similar plot profiles reflect significant performance differences. For instance users with 60K mentions on twitter are identified using Sparksee in only 0.3 seconds.

In the paper the authors also discuss other queries like the built-in shortest path algorithms of both databases. Sparksee has improved its performance in the latest version 5.2.

In case you are interested in more details, please check the complete article here. If you are interested in benchmarking Sparksee or using it to leverage your Research do not hesitate to ask us for a free license under our Research program!

(*) Experiments from the paper were conducted on a standard Intel Core 2 Duo 3.0 Ghz and 8GB RAM with a non-SSD HDD. Neo4j v2.2M03 & Sparksee v5.1