International audience

International audience

Social networks (SN) are omnipresent in our lives today. Not all users have the same behaviour on these networks. If some have a low activity, rarely posting messages and following few users, some others at the other extreme have a significant activity, with many followers and regularly posts. The important role of these popular SN users makes them the target of many applications for example for content monitoring or advertising. It is therefore relevant to be able to predict as soon as possible which SN users will become popular.

Abstract To maximize the impact of an advertisement campaign on social networks, the real-time bidding (RTB) systems aim at targeting the most influential users of this network. Influence maximization (IM) is a solution that addresses this issue by maximizing the coverage of the network with top-k influencers who maximize the diffusion of information. Associated with online advertising strategies at Web scale, RTB is faced with complex ad placement decisions in real time to deal with a high-speed stream of online users. To tackle this issue, IM strategies should be modified in order to integrate RTB constraints. While most traditional IM methods deal with static sets of top influencers, they hardly address the dynamic influence targeting issue by integrating short time decision, no interchange and stream’s incompleteness. This paper proposes a real-time influence maximization approach which takes influence maximization decisions within a real-time bidding environment. A deep analysis of influence scores of users over several social networks is presented as well a strategy to guarantee the impact of an IM strategy in order to define the budget of an ad campaign. Finally, we offer a thorough experimental process to compare static versus dynamic IM solutionswrt. influence scores.

International audience

Several distributed frameworks have recently emerged to perform computations on large-scale graphs. However some recent studies have highlighted that vertex-partitioning approaches, e.g. Giraph, failed to achieve workload-balanced partitioning for skewed graphs, typically having a heavy-tail degree distribution. While edge-partitioning approaches such as PowerGraph and GraphX provide beter balancing and performances for graph computation, they supply a generic framework, independent from the computation. This demonstration presents SGVCut to display our edge partitions designed for random walks-based computation, which is the foundation of many graph algorithms, on skewed graphs. The demonstration scenario introduces SGVCut interface and illustrates the benefits of our approach compare to other partitioning strategies for different settings and algorithms.

International audience

Publish/Subscribe (Pub/Sub) systems have been designed to face the exponential growth of information published on the Web by subscribing to sources of interest which produce flows of items. However users may receive some information several times, or information that does not contain any new content, and conversely miss some information of interest hidden in all information received. Pub/Sub systems are consequently witnessing a real challenge to efficiently filter relevant information. We propose in this paper a scalable approach for filtering news (items) which match the user interests (expressed as subscriptions). Introducing for the first time Term Discrimination Value (TDV) in this context, which allows to measure how a term discrimines an item, we filter out in real-time items whose content has already been notified recently to the user, either in another item (filtering by novelty) or globally in his recent history (filtering by diversity). Our experiments illustrate the impact of our different parameters and confirm the scalability of our approach and the relevance of the results notified.

Content syndication has become a popular way for timely delivery of frequently updated information on the Web. It essentially enhances traditional pull-oriented searching and browsing of web pages with push-oriented protocols. However many Web syndication applications imply a tight coupling between feed producers and consumers and do not help users to find, in all information they received, items with interesting and new content. We present the FiND Pub/Sub system which integrates an in-memory filtering process based on keyword subscriptions. Unlike existing proposals, FiND is designed for real-time notifications on item streams. This demonstration illustrates the main features of the FiND system namely (i) a scalable real-time notification process when the most important terms of the subscription are matched, (ii) a tunable filtering by novelty and diversity to reduce user flooding.

Social networks have become an important information source. Due to their unprecedented success, these systems have to face an exponentially increasing amount of user generated content. As a consequence, finding relevant users or data matching specific interests is a challenging. We present RecLand, a recommender system that takes advantage of the social graph topology and of the existing contextual information to recommend users. The graphical interface of RecLand shows recommendations that match the topical interests of users and allows to tune the parameters to adapt the recommendations to their needs.

The demonstration is devoted to the desktop-level interactions offered by Cador, a content-based document management system currently under development. Cador provides a rule-based language to query and manipulate large collections of documents distributed in repositories. The language is able to define the content of Virtual File Systems (VFS) as views over the document collections. This feature allows users to combine their familiar interface and desktop-based softwares with the powerful search and transformation tools provided by the underlying system.

The explosion of published information on the Web leads to the emergence of a Web syndication paradigm, which transforms the passive reader into an active information collector. Information consumers subscribe to RSS/Atom feeds and are notified whenever a piece of news (item) is published. The success of this Web syndication now offered on Web sites, blogs, and social media, however raises scalability issues. There is a vital need for efficient real-time filtering methods across feeds, to allow users to follow effectively personally interesting information. We investigate in this paper three indexing techniques for users' subscriptions based on inverted lists or on an ordered trie. We present analytical models for memory requirements and matching time and we conduct a thorough experimental evaluation to exhibit the impact of critical workload parameters on these structures.

AS-Index is a new index structure for exact string search in disk resident databases. It uses hashing, unlike known alternatives, whether baesd on trees or tries. It typically indexes every n-gram in the database, though non-dense indexing is possible. The hash function uses the algebraic signatures of n-grams. Use of hashing provides for constant index access time for arbitrarily long patterns, unlike other structures whose search cost is at best logarithmic. The storage overhead of AS-Index is basically 500 - 600%, similar to that ofalternatives or smaller. We show the index structure, our use of algebraic signatures and the search algorithm. We present the theoretical and experimental performance analysis. We compare the AS-Index to main alternatives. We conclude that AS-Index is an attractive structure and we indicate directions for future work.

We propose a general framework to index very large datasets of spatial data in a distributed system. Our proposal is built on the recently proposed Scalable Distributed Rtree (SD-Rtree) [4] and addresses specifically the server allocation problem. In SD-Rtree, a new server is assigned to the network whenever a split of a full node is required. We describe a more flexible allocation protocol which copes with a temporary shortage of storage resources. Our algorithm is especially based on k-NN query processing we introduce as well. We analyze the cost of this protocol, describe its features, and propose practical hints to use it. We also present experiments validating our approach.

We propose a scalable distributed data structure (SDDS) called SD-Rtree. We intend our structure for point and window queries over possibly large spatial datasets distributed on clusters of interconnected servers. SD-Rtree generalizes the well-known Rtree structure. It uses a distributed balanced binary spatial tree that scales with insertions to potentially any number of storage servers through splits of the overloaded ones. A user/application manipulates the structure from a client node. The client addresses the tree through its image that the splits can make outdated. This may generate addressing errors, solved by the forwarding among the servers. Specific messages towards the clients incrementally correct the outdated images.

We consider an environment where a subscription system continuously evaluates pattern-based requests over unbounded sequential data. We propose an extension of the traditional pattern-matching techniques for efficiently handling large sets of such continuous queries. This extension relies on the introduction of variables in patterns in order to augment their expressivity. Based on this extended class of parameterized queries, our main contributions are threefold. First, we define a refinement relation based on variable relaxation. Second, we use the semi-lattice structure of the set of parameterized patterns for patterns aggregation and filtering. We propose an on-line pattern aggregation algorithm so as to both reduce the cost of pattern-matching evaluation as well as to filter out sequences that cannot match any of the patterns in a subscription cluster. Finally we show, through analysis and experiments, that our technique reduces quite effectively the cost of the matching process

Many applications rely on sequence databases and use extensively pattern-matching queries to retrieve data of interest. This paper extends the traditional pattern-matching expressions to parameterized patterns, featuring variables. Parameterized patterns are more expressive and allow to define concisely regular expressions that would be very complex to describe without variables. They can also be used to express additional constraints on patterns' variables.We show that they can be evaluated without additional cost with respect to traditional techniques (e.g., the Knuth-Morris-Pratt algorithm). We describe an algorithm that enjoys low memory and CPU time requirements, and provide experimental results which illustrate the gain of the optimized solution.