OpenRaiser/Intern-Atlas huggingface dataset:
Distributed social graph embedding
Authors: Anne-Marie Kermarrec, Vincent Leroy, Gilles Trédan
Venue: CIKM
Year: 2011

Distributed recommender systems are becoming increasingly important for they address both scalability and the Big Brother syndrome. Link prediction is one of the core mechanism in recommender systems and relies on extracting some notion of proximity between entities in a graph. Applied to social networks, defining a proximity metric between users enable to predict potential relevant future relationships. In this paper, we propose SoCS (Social Coordinate Systems}, a fully distributed algorithm that embeds any social graph in an Euclidean space, which can easily be used to implement link prediction. To the best of our knowledge, SoCS is the first system explicitly relying on graph embedding. Inspired by recent works on non-isomorphic embeddings, the SoCS embedding preserves the community structure of the original graph, while being easy to decentralize. Nodes thus get assigned coordinates that reflect their social position. We show through experiments on real and synthetic data sets that these coordinates can be exploited for efficient link prediction.
Approximate tensor decomposition within a tensor-relational algebraic framework
Authors: Mijung Kim, Kasim Selçuk Candan
Venue: CIKM
Year: 2011

In this paper, we first introduce a tensor-based relational data model and define algebraic operations on this model. We note that, while in traditional relational algebraic systems the join operation tends to be the costliest operation of all, in the tensor-relational framework presented here, tensor decomposition becomes the computationally costliest operation. Therefore, we consider optimization of tensor decomposition operations within a relational algebraic framework. This leads to a highly efficient, effective, and easy-to-parallelize join-by-decomposition approach and a corresponding KL-divergence based optimization strategy. Experimental results provide evidence that minimizing KL-divergence within the proposed join-by-decomposition helps approximate the conventional join-then-decompose scheme well, without the associated time and space costs.
Evaluating an associative browsing model for personal information
Authors: Jin Young Kim, W. Bruce Croft, David A. Smith, Anton Bakalov
Venue: CIKM
Year: 2011

Recent studies suggest that associative browsing can be beneficial for personal information access. Associative browsing is intuitive for the user and complements other methods of accessing personal information, such as keyword search. In our previous work, we proposed an associative browsing model of personal information in which users can navigate through the space of documents and concepts (e.g., person names, events, etc.). Our approach differs from other systems in that it presented a ranked list of associations by combining multiple measures of similarity, whose weights are improved based on click feedback from the user.
Mining entity translations from comparable corpora: a holistic graph mapping approach
Authors: Jinhan Kim, Long Jiang, Seung-won Hwang, Young-In Song, Ming Zhou
Venue: CIKM
Year: 2011

This paper addresses the problem of mining named entity translations from comparable corpora, specifically, mining English and Chinese named entity translation. We first observe that existing approaches use one or more of the following named entity similarity metrics: entity, entity context, and relationship. Inspired by this observation, in this paper, we propose a new holistic approach, by (1) combining all similarity types used and (2) additionally considering relationship context similarity between pairs of named entities, a missing quadrant in the taxonomy of similarity metrics. We abstract the named entity translation problem as the matching of two named entity graphs extracted from the comparable corpora. Specifically, named entity graphs are first constructed from comparable corpora to extract relationship between named entities. Entity similarity and entity context similarity are then calculated from every pair of bilingual named entities. A reinforcing method is utilized to reflect relationship similarity and relationship context similarity between named entities. According to our experimental results, our holistic graph-based approach significantly outperforms previous approaches.
Spectral analysis of a blogosphere
Authors: Sang-Wook Kim, Ki-Nam Kim, Christos Faloutsos, Joon Ho Lee
Venue: CIKM
Year: 2011

A blogosphere is a representative example of online social networks. In this paper, we address spectral analysis of a blogosphere. We model a real-world blogosphere as a matrix and a tensor, and then analyze it by using the SVD and PARAFAC decomposition. According to the results, the SVD successfully identified communities, each of which focuses on a specific topic, and also found hub blogs and authoritative posts within each community. The PARAFAC decomposition also succeeded in extracting more communities of finer granules than the SVD. Also, the PARAFAC decomposition could identify the dominant keywords in addition to the hub blogs and authoritative posts honored in each community.
Accounting for data dependencies within a hierarchical dirichlet process mixture model
Authors: Dongwoo Kim, Alice Oh
Venue: CIKM
Year: 2011

We propose a hierarchical nonparametric topic model, based on the hierarchical Dirichlet process (HDP), that accounts for dependencies among the data. The HDP mixture models are useful for discovering an unknown semantic structure (i.e., topics) from a set of unstructured data such as a corpus of documents. For simplicity, HDP makes an exchangeability assumption that any permutation of the data points would result in the same joint probability of the data being generated. This exchangeability assumption poses a problem for some domains where there are clear and strong dependencies among the data. A model that allows for non-exchangeability of data can capture these dependencies and assign higher probabilities to clusters that account for data dependencies, for example, inferring topics that reflect the temporal patterns of the data. Our model incorporates the distance dependent Chinese restaurant process (ddCRP), which clusters data with an inherent bias toward clusters of data points that are near to one another, into a hierarchical construction analogous to the HDP, and we call this new prior the distance dependent Chinese restaurant franchise (ddCRF). When tested with temporal datasets, the ddCRF mixture model shows clear improvements in data fit compared to the HDP in terms of heldout likelihood and complexity. The resulting set of topics shows the sequential emergence and disappearance patterns of topics.
Advertiser-centric approach to understand user click behavior in sponsored search
Authors: Sungchul Kim, Tao Qin, Hwanjo Yu, Tie-Yan Liu
Venue: CIKM
Year: 2011

Sponsored search is the major business model of commercial search engines. The number of clicks on ads is a key indicator of success for both advertisers and search engines, and increasing ad clicks is a goal of both of them. Many existing works stand on the view of search engines concerning how to help search engines to earn more revenue by accurately predicting ad clicks. Unlike the existing works, this paper aims at understanding user clicks on ads from "the view of advertisers", in order to help advertisers to improve their ad quality and therefore advertising effectiveness. To do this, a factor graph model is proposed, which considers two advertiser-controllable factors to understand user click behaviors: the relevance between a query and an ad, which has been well studied in previous literatures, and the "attractiveness" of the ad, which is a newly-proposed concept. The proposed model can be used to predict user clicks and also to mine a set of attractive words that could be leveraged to improve the quality of the ads. We have verified the effectiveness of the proposed approach using real-world datasets, through quantitative evaluations and informative case studies.
Mining query structure from click data: a case study of product queries
Authors: Julia Kiseleva, Eugene Agichtein, Daniel Billsus
Venue: CIKM
Year: 2011

Most of the information on the Web is inherently structured, product pages of large online shopping sites such as Amazon.com being a typical example. Yet, unstructured keyword queries are still the most common way to search for such structured information, producing an ambiguities and poor ranking, and by that degrading user experience. This problem can be resolved by query segmentation, that is, transformation of unstructured keyword queries into structured queries. The resulting queries can be used to search product databases more accurately, and improve result presentation and query suggestion. The main contribution of our work is a novel approach to query segmentation based on unsupervised machine learning. Its highlight is that query and click-through logs are used for training. Extensive experiments over a large query and click log from a leading shopping engine demonstrate that our approach significantly outperforms baseline.
Block-based load balancing for entity resolution with MapReduce
Authors: Lars Kolb, Andreas Thor, Erhard Rahm
Venue: CIKM
Year: 2011

The effectiveness and scalability of MapReduce-based implementations of complex data-intensive tasks depend on an even redistribution of data between map and reduce tasks. In the presence of skewed data, sophisticated redistribution approaches thus become necessary to achieve load balancing among all reduce tasks to be executed in parallel. For the complex problem of entity resolution with blocking, we propose BlockSplit, a load balancing approach that supports blocking techniques to reduce the search space of entity resolution. The evaluation on a real cloud infrastructure shows the value and effectiveness of the proposed approach.
One is enough: distributed filtering for duplicate elimination
Authors: Georgia Koloniari, Nikos Ntarmos, Evaggelia Pitoura, Dimitris Souravlias
Venue: CIKM
Year: 2011

The growth of online services has created the need for duplicate elimination in high-volume streams of events. The sheer volume of data in applications such as pay-per-click clickstream processing, RSS feed syndication and notification services in social sites such Twitter and Facebook makes traditional centralized solutions hard to scale. In this paper, we propose an approach based on distributed filtering. To this end, we introduce a suite of distributed Bloom filters that exploit different ways of partitioning the event space. To address the continuous nature of event delivery, the filters are extended to support sliding window semantics. Moreover, we examine locality-related tradeoffs and propose a tree-based architecture to allow for duplicate elimination across geographic locations. We cast the design space and present experimental results that demonstrate the pros and cons of our various solutions in different settings.
Robust nonnegative matrix factorization using L21-norm
Authors: Deguang Kong, Chris H. Q. Ding, Heng Huang
Venue: CIKM
Year: 2011

Nonnegative matrix factorization (NMF) is widely used in data mining and machine learning fields. However, many data contain noises and outliers. Thus a robust version of NMF is needed. In this paper, we propose a robust formulation of NMF using L21 norm loss function. We also derive a computational algorithm with rigorous convergence analysis. Our robust NMF approach, (1) can handle noises and outliers; (2) provides very efficient and elegant updating rules; (3) incurs almost the same computational cost as standard NMF, thus potentially to be used in more real world application tasks. Experiments on 10 datasets show that the robust NMF provides more faithful basis factors and consistently better clustering results as compared to standard NMF.
On the elasticity of NoSQL databases over cloud management platforms
Authors: Ioannis Konstantinou, Evangelos Angelou, Christina Boumpouka, Dimitrios Tsoumakos, Nectarios Koziris
Venue: CIKM
Year: 2011

NoSQL databases focus on analytical processing of large scale datasets, offering increased scalability over commodity hardware. One of their strongest features is elasticity, which allows for fairly portioned premiums and high-quality performance and directly applies to the philosophy of a cloud-based platform. Yet, the process of adaptive expansion and contraction of resources usually involves a lot of manual effort during cluster configuration. To date, there exists no comparative study to quantify this cost and measure the efficacy of NoSQL engines that offer this feature over a cloud provider. In this work, we present a cloud-enabled framework for adaptive monitoring of NoSQL systems. We perform a study of the elasticity feature on some of the most popular NoSQL databases over an open-source cloud platform. Based on these measurements, we finally present a prototype implementation of a decision making system that enables automatic elastic operations of any NoSQL engine based on administrator or application-specified constraints.
Interactive sense feedback for difficult queries
Authors: Alexander Kotov, ChengXiang Zhai
Venue: CIKM
Year: 2011

Ambiguity of query terms is a common cause of inaccurate retrieval results. Existing work has mostly focused on studying how to improve retrieval accuracy by automatically resolving word sense ambiguity. However, fully automatic sense identification and disambiguation is a very challenging task. In this work, we propose to involve a user in the process of disambiguation through interactive sense feedback and study the potential effectiveness of this novel feedback strategy. We propose several general methods to automatically identify the major senses of query terms based on global analysis of document collection and generate concise representations of the discovered senses to the users. This feedback strategy does not rely on initial retrieval results, and thus can be especially useful for improving the results of difficult queries. We evaluated the effectiveness of the proposed methods for sense identification and presentation through simulation experiments and user studies, which both indicate that sense feedback strategy is a promising alternative to the existing interactive feedback techniques such as relevance feedback and term feedback.
Advances in data stream mining for mobile and ubiquitous environments
Authors: Shonali Krishnaswamy, João Gama, Mohamed Medhat Gaber
Venue: CIKM
Year: 2011

The tutorial presents the state-of-the-art in mobile and ubiquitous data stream mining and discusses open research problems, issues, and challenges in this area.
Processing the signature quadratic form distance on many-core GPU architectures
Authors: Martin Krulis, Jakub Lokoc, Christian Beecks, Tomás Skopal, Thomas Seidl
Venue: CIKM
Year: 2011

The Signature Quadratic Form Distance on feature signatures represents a flexible distance-based similarity model for effective content-based multimedia retrieval. Although metric indexing approaches are able to speed up query processing by two orders of magnitude, their applicability to large-scale multimedia databases containing billions of images is still a challenging issue. In this paper, we propose the utilization of GPUs for efficient query processing with the Signature Quadratic Form Distance. We show how to process multiple distance computations in parallel and demonstrate efficient query processing by comparing many-core GPU with multi-core CPU implementations.
Index structures and top-k join algorithms for native keyword search databases
Authors: Günter Ladwig, Thanh Tran
Venue: CIKM
Year: 2011

For supporting keyword search on structured data, current solutions require large indexes to be built that redundantly store subgraphs called neighborhoods. Further, for exploring keyword search results, large graphs have to be loaded into memory. We propose a solution, which employs much more compact index structures for neighborhood lookups. Using these indexes, we reduce keyword search result exploration to the traditional database problem of top-k join processing, enabling results to be computed efficiently. In particular, this computation can be performed on data streams successively loaded from disk (i.e., does not require the entire input to be loaded at once into memory). For supporting this, we propose a top-k procedure based on the rank join operator, which not only computes the k-best results, but also selects query plans in a top-k fashion during the process. In experiments using large real-world datasets, our solution reduced storage requirements and also outperformed the state-of-the-art in terms of performance and scalability.
Attention prediction on social media brand pages
Authors: Himabindu Lakkaraju, Jitendra Ajmera
Venue: CIKM
Year: 2011

In this paper, we deal with the problem of predicting how much attention a newly submitted post would receive from fellow community members of closed communities in social networking sites. Though the concept of attention is subjective, the number of comments received by a post serves as a very good indicator of the same. Unlike previous work which primarily made use of either content features or the network features (friendship links on the network), we exploit both the content features and community level features (for instance, what time of the day is the community more active) for tackling this problem. Further, we focus on dedicated pages of corporate brands on social media websites and accordingly extract important features from the content and community activity of such brand pages. The attention prediction task finds direct application in the listening, monitoring and engaging activities of the businesses that have such brand-pages. In this paper, we formulate the problem of attention prediction on social media brand pages.
Frequency-aware similarity measures: why Arnold Schwarzenegger is always a duplicate
Authors: Dustin Lange, Felix Naumann
Venue: CIKM
Year: 2011

Measuring the similarity of two records is a challenging problem, but necessary for fundamental tasks, such as duplicate detection and similarity search. By exploiting frequencies of attribute values, many similarity measures can be improved: In a person table with U.S. citizens, Arnold Schwarzenegger is a very rare name. If we find several Arnold Schwarzeneggers in it, it is very likely that these are duplicates. We are then less strict when comparing other attribute values, such as birth date or address. We put this intuition to use by partitioning compared record pairs according to frequencies of attribute values. For example, we could create three partitions from our data: Partition 1 contains all pairs with rare names, Partition 2 all pairs with medium frequent names, and Partition 3 all pairs with frequent names. For each partition, we learn a different similarity measure: we apply machine learning techniques to combine a set of base similarity measures into an overall measure. To determine a good partitioning, we compare different partitioning strategies. We achieved best results with a novel algorithm inspired by genetic programming.
Efficient similarity search: arbitrary similarity measures, arbitrary composition
Authors: Dustin Lange, Felix Naumann
Venue: CIKM
Year: 2011

Given a (large) set of objects and a query, similarity search aims to find all objects similar to the query. A frequent approach is to define a set of base similarity measures for the different aspects of the objects, and to build light-weight similarity indexes on these measures. To determine the overall similarity of two objects, the results of these base measures are composed, e.g., using simple aggregates or more involved machine learning techniques. We propose the first solution to this search problem that does not place any restrictions on the similarity measures, the composition technique, or the data set size. We define the query plan optimization problem to determine the best query plan using the similarity indexes. A query plan must choose which individual indexes to access and which thresholds to apply. The plan result should be as complete as possible within some cost threshold. We propose the approximative top neighborhood algorithm, which determines a near-optimal plan while significantly reducing the amount of candidate plans to be considered. An exact version of the algorithm determines the optimal solution. Evaluation on real-world data indicates that both versions clearly outperform a complete search of the query plan space.
Leveraging web 2.0 data for scalable semi-supervised learning of domain-specific sentiment lexicons
Authors: Raymond Yiu-Keung Lau, Chun Lam Lai, Peter Bruza, Kam-Fai Wong
Venue: CIKM
Year: 2011

Since manually constructing domain-specific sentiment lexicons is extremely time consuming and it may not even be feasible for domains where linguistic expertise is not available, research on automatic construction of domain-specific sentiment lexicons has become a hot topic in recent years. The main contribution of this paper is the illustration of a novel semi-supervised learning method which exploits both term-to-term and document-to-term relations hidden in a corpus for the construction of domain-specific sentiment lexicons. More specifically, the proposed two-pass pseudo labeling method combines shallow linguistic parsing and corpus-base statistical learning to make domain-specific sentiment extraction scalable with respect to the sheer volume of opinionated documents archived on the Internet these days. Our experiments show that the proposed method can generate high quality domain-specific sentiment lexicons according to users' evaluation.
Collaborative blacklist generation via searches-and-clicks
Authors: Lung-Hao Lee, Hsin-Hsi Chen
Venue: CIKM
Year: 2011

This paper presents an intent conformity model to collaboratively generate blacklists for cyberporn filtering. A novel porn detection framework via searches-and-clicks is proposed to explore collective intelligence embedded in query logs. Firstly, the clicked pages are represented in terms of the weighted queries to reflect the degrees related to pornography. Consequently, these weighted queries are regarded as discriminative features to calculate the pornography indicator by an inverse chi-square method for candidate determination. Finally, a candidate whose URL contains at least one pornographic keyword is included in our collaborative blacklists. The experiments on a MSN porn data set indicate that the generated blacklist achieves a high precision, while maintaining a favorably low false positive rate. In addition, real-life filtering simulations reveal that our blacklist is more effective than some publicly released blacklists.