OpenRaiser/Intern-Atlas huggingface dataset:
Assisting web search users by destination reachability
Authors: Chi-Hoon Lee, Alpa Jain, Larry Lai
Venue: CIKM
Year: 2011

Search engine users are increasingly performing complex tasks based on the simple keyword-in document-out paradigm. To assist users in accomplishing their tasks effectively, search engines provide query recommendations based on the user's current query. These are suggestions for follow-up queries given the user-provided query. A large number of techniques have been proposed in the past on mining such query recommendations which include past user sessions (e.g., sequence of queries within a specified window of time) to identify most frequently occurring pairs, using click-through graphs (e.g., a bipartite graph of queries and the urls on which users clicked) and rank these suggestions using some form of frequency counts from the past query logs. Given the limited number of queries that are offered (typically 5) it is important to effectively rank them. In this paper, we present a novel approach to ranking query recommendations which not only consider relevance to the original query but also take into account efficiency of a query at accomplishing a user search task at hand. We formalize the notion of query efficiency and show how our objective function effectively captures this as determined by a human study and eliminates biases introduced by click-through based metrics. To compute this objective function, we present a pseudosupervised learning technique where no explicit human experts are required to label samples. In addition, our techniques effectively characterize preferred url destinations and project each query into a higher dimension space where each sub-spaces represents user intent using these characteristics. Finally, we present an extensive evaluation of our proposed methods against production systems and show our method to increase task completion efficiency by 15%.
Scalable entity matching computation with materialization
Authors: Sanghoon Lee, Jongwuk Lee, Seung-won Hwang
Venue: CIKM
Year: 2011

Entity matching (EM) is the task of identifying records that refer to the same real-world entity from different data sources. While EM is widely used in data integration and data cleaning applications, the naive method for EM incurs quadratic cost with respect to the size of the datasets. To address this problem, this paper proposes a scalable EM algorithm that employs a pre-materialized structure. Specifically, once the structure is built, our proposed algorithm can identify the EM results with sub-linear cost. In addition, as the rules evolve, our algorithm can efficiently adapt to new rules by selectively accessing records using the materialized structure. Our evaluation results show that our proposed EM algorithm is significantly faster than the state-of-the-art method for extensive real-life datasets.
Robust video fingerprinting based on hierarchical symmetric difference feature
Authors: Jungho Lee, Seungjae Lee, Yongseok Seo, Wonyoung Yoo
Venue: CIKM
Year: 2011

The piracy of copyrighted digital content over the Internet infringes copyrights and damages the digital content industry. Accordingly, identifying and monitoring technology on the online content service like fingerprinting is getting valuable through the explosion of digital content sharing. This paper proposes a robust video fingerprinting feature to identify a modified video clip from a large scale database. Hierarchical symmetric difference feature is proposed in order to offer efficient video fingerprinting. The feature is robust and pairwise independent against various video modifications such as compression, resizing, or cropping. Moreover, videos undergoing a transformation such as flipping or mirroring can be identified by simply disordering the bit pattern of fingerprints. The performance of the proposed feature is extensively experimented on 6,482 hours of database and the experimental results show that the proposed fingerprinting is efficient and robust against various modifications.
Named entity recognition using a modified Pegasos algorithm
Authors: Changki Lee, Pum-Mo Ryu, Hyunki Kim
Venue: CIKM
Year: 2011

In this paper, we describe a named entity recognition using a modified Pegasos algorithm for structural SVMs. We show the modified Pegasos algorithm significantly outperformed CRFs and the training time for the modified Pegasos algorithm is reduced 17-26 times compared to CRFs.
Duplicate detection through structure optimization
Authors: Luís Leitão, Pável Calado
Venue: CIKM
Year: 2011

Detecting and eliminating duplicates in databases is a task of critical importance in many applications. Although solutions for traditional models, such as relational data, have been widely studied, recently there has been some focus on solutions for more complex hierarchical structures as, for instance, XML data. Such data presents many different challenges, among which is the issue of how to exploit the schema structure to determine if two objects are duplicates. In this paper, we argue that structure can indeed have a significant impact on the process of duplicate detection. We propose a novel method that automatically restructures database objects in order to take full advantage of the relations between its attributes. This new structure reflects the relative importance of the attributes in the database and avoids the need to perform a manual selection. To test our approach we applied it to an existing duplicate detection system. Experiments performed on several datasets show that, using the new learned structure, we consistently outperform both the results obtained with the original database structure and those obtained by letting a knowledgeable user manually choose the attributes to compare.
Ontology-based data management
Authors: Maurizio Lenzerini
Venue: CIKM
Year: 2011

Ontology-based data management aims at accessing and using data by means of an ontology, i.e., a conceptual representation of the domain of interest in the underlying information system. This new paradigm provides several interesting features, many of which have been already proved effective in managing complex information systems. On the other hand, several important issues remain open, and constitute stimulating challenges for the research community. In this talk we first provide an introduction to ontology-based data management, illustrating the main ideas and techniques for using an ontology to access the data layer of an information system, and then we discuss several important issues that are still the subject of extensive investigations, including the need of inconsistency tolerant query answering methods, and the need of supporting update operations expressed over the ontology.
Joint inference for cross-document information extraction
Authors: Qi Li, Sam Anzaroot, Wen-Pin Lin, Xiang Li, Heng Ji
Venue: CIKM
Year: 2011

Previous information extraction (IE) systems are typically organized as a pipeline architecture of separated stages which make independent local decisions. When the data grows beyond some certain size, the extracted facts become inter-dependent and thus we can take advantage of information redundancy to conduct reasoning across documents and improve the performance of IE. We describe a joint inference approach based on information network structure to conduct cross-fact reasoning with an integer linear programming framework. Without using any additional labeled data this new method obtained 13.7%-24.4% user browsing cost reduction over a state-of-the-art IE system which extracts various types of facts independently.
CASINO: towards conformity-aware social influence analysis in online social networks
Authors: Hui Li, Sourav S. Bhowmick, Aixin Sun
Venue: CIKM
Year: 2011

Social influence analysis in online social networks is the study of people's influence by analyzing the social interactions between individuals. There have been increasing research efforts to understand the influence propagation phenomenon due to its importance to information dissemination among others. Despite the progress achieved by state-of-the-art social influence analysis techniques, a key limitation of these techniques is that they only utilize positive interactions (e.g., agreement, trust) between individuals, ignoring two equally important factors, namely, negative relationships (e.g., distrust, disagreement) between individuals and conformity of people, which refers to a person's inclination to be influenced. In this paper, we propose a novel algorithm CASINO (Conformity-Aware Social INfluence cOmputation) to study the interplay between influence and conformity of each individual. Given a social network, CASINO first extracts a set of topic-based subgraphs where each subgraph depicts the social interactions associated with a specific topic. Then it optionally labels the edges (relationships) between individuals with positive or negative signs. Finally, it computes the influence and conformity indices of each individual in each signed topic-based subgraph. Our empirical study with several real-world social networks demonstrates superior effectiveness and accuracy of CASINO compared to state-of-the-art methods. Furthermore, we revealed several interesting characteristics of "influentials" and "conformers" in these networks.
A cluster based mobile peer to peer architecture in wireless ad hoc networks
Authors: He Li, Kyoungsoo Bok, Jaesoo Yoo
Venue: CIKM
Year: 2011

With the rapid development of wireless communication technologies and mobile devices, the mobile peer to peer (MP2P) network has been emerged. Since the existing MP2P architectures have high management cost, in this paper, we propose a hierarchical MP2P architecture using clustering mobile peers. The proposed method clusters the mobile peers by considering three aspects like the maximum connection time, the minimum hop count and the number of the connected peers. The connection times between the connected peers can be determined by the location, velocity vector and communication range of the mobile peers. Since the maximum connection time of the connected peers are considered, the network topology is relatively stable. Therefore, the management cost of the network is decreased and the success rate of contents search is increased. Experiments have shown that our proposed method outperforms the existing schemes.
Collaborative online learning of user generated content
Authors: Guangxia Li, Kuiyu Chang, Steven C. H. Hoi, Wenting Liu, Ramesh C. Jain
Venue: CIKM
Year: 2011

We study the problem of online classification of user generated content, with the goal of efficiently learning to categorize content generated by individual user. This problem is challenging due to several reasons. First, the huge amount of user generated content demands a highly efficient and scalable classification solution. Second, the categories are typically highly imbalanced, i.e., the number of samples from a particular useful class could be far and few between compared to some others (majority class). In some applications like spam detection, identification of the minority class often has significantly greater value than that of the majority class. Last but not least, when learning a classification model from a group of users, there is a dilemma: A single classification model trained on the entire corpus may fail to capture personalized characteristics such as language and writing styles unique to each user. On the other hand, a personalized model dedicated to each user may be inaccurate due to the scarcity of training data, especially at the very beginning; when users have written just a few articles. To overcome these challenges, we propose learning a global model over all users' data, which is then leveraged to continuously refine the individual models through a collaborative online learning approach. The class imbalance problem is addressed via a cost-sensitive learning approach. Experimental results show that our method is effective and scalable for timely classification of user generated content.
YANA: an efficient privacy-preserving recommender system for online social communities
Authors: Dongsheng Li, Qin Lv, Li Shang, Ning Gu
Venue: CIKM
Year: 2011

In online social communities, many recommender systems use collaborative filtering, a method that makes recommendations based on what are liked by other users with similar interests. Serious privacy issues may arise in this process, as sensitive personal information (e.g., content interests) may be collected and disclosed to other parties, especially the recommender server. In this paper, we propose YANA (short for "you are not alone"), an efficient group-based privacy-preserving collaborative filtering system for content recommendation in online social communities. We have developed a prototype system on desktop and mobile devices, and evaluated it using real world data. The results demonstrate that YANA can effectively protect users' privacy, while achieving high recommendation quality and energy efficiency.
Context-based entity description rule for entity resolution
Authors: Lingli Li, Jianzhong Li, Hongzhi Wang, Hong Gao
Venue: CIKM
Year: 2011

In this paper, we consider the entity resolution(ER) problem, which is to identify objects referring to the same real-world entity. Prior work of ER involves expensive similarity comparison and clustering approaches. Additionally, the quality of entity resolution may be low due to insufficient information. To address these problems, by adopting context information of data objects, we present a novel framework of entity resolution, context-based entity description (CED), to make context information help entity resolution. In our framework, each entity is described by a set of CEDs. During entity resolution, objects are only compared with CEDs to determine its corresponding entity. Additionally, we propose efficient algorithms for CED discovery and CED-based entity resolution. We experimentally evaluated our CED-based ER algorithm on the real DBLP datasets, and the experimental results show that our algorithm can achieve both high precision and recall as well as outperform existing methods.
Context-based people search in labeled social networks
Authors: Cheng-Te Li, Man-Kwan Shan, Shou-De Lin
Venue: CIKM
Year: 2011

In online social networking services, there are a range of scenarios in which users want to search a particular person given the targeted person one's name. The challenge of such people search is namesake, which means that there are many people possess the same names in the social network. In this paper, we propose to leverage the query contexts to tackle such problems. For example, given the information of one's graduation year and city, the last names of some individuals, one may wish to find classmates from his/her high school. We formulate such problem as the context-based people search. Given a social network in which each node is associated with a set of labels and given a query set of labels consisting of a targeted name label and other context labels, our goal is to return a ranking list of persons who possess the targeted name label and connects to other context labels with minimum communication costs through an effective subgraph in the social network. We consider the interactions among query labels to propose a grouping-based method to solve the context-based people search. Our method consists of three major parts. First, we model those nodes with query labels into a group graph which is able to reduce the search space to enhance the time efficiency. Second, we identify three different kinds of connectors which connecting different groups, and exploit connectors to find the corresponding detailed graph topology from the group graph. Third, we propose a Connector-Steiner Tree algorithm to retrieve a resulting ranked list of individuals who possess the targeted label. Experimental results on the DBLP bibliography data show that our grouping-based method can reach the good quality of returned persons as a greedy search algorithm at a considerable outperformance on the time efficiency.
The where in the tweet
Authors: Wen Li, Pavel Serdyukov, Arjen P. de Vries, Carsten Eickhoff, Martha A. Larson
Venue: CIKM
Year: 2011

Twitter is a widely-used social networking service which enables its users to post text-based messages, so-called tweets. POI tags on tweets can show more human-readable high-level information about a place rather than just a pair of coordinates. In this paper, we attempt to predict the POI tag of a tweet based on its textual content and time of posting. Potential applications include accurate positioning when GPS devices fail and disambiguating places located near each other. We consider this task as a ranking problem, i.e., we try to rank a set of candidate POIs according to a tweet by using language and time models. To tackle the sparsity of tweets tagged with POIs, we use web pages retrieved by search engines as an additional source of evidence. From our experiments, we find that users indeed leak some information about their accurate locations in their tweets.
Learning-based relevance feedback for web-based relation completion
Authors: Zhixu Li, Laurianne Sitbon, Xiaofang Zhou
Venue: CIKM
Year: 2011

In a pilot application based on web search engine called Web-based Relation Completion (WebRC), we propose to join two columns of entities linked by a predefined relation by mining knowledge from the web through a web search engine. To achieve this, a novel retrieval task Relation Query Expansion (RelQE) is modelled: given an entity (query), the task is to retrieve documents containing entities in predefined relation to the given one. Solving this problem entails expanding the query before submitting it to a web search engine to ensure that mostly documents containing the linked entity are returned in the top K search results. In this paper, we propose a novel Learning-based Relevance Feedback (LRF) approach to solve this retrieval task. Expansion terms are learned from training pairs of entities linked by the predefined relation and applied to new entity-queries to find entities linked by the same relation. After describing the approach, we present experimental results on real-world web data collections, which show that the LRF approach always improves the precision of top-ranked search results to up to 8.6 times the baseline. Using LRF, WebRC also shows performances way above the baseline.
Exploring categorization property of social annotations for information retrieval
Authors: Peng Li, Bin Wang, Wei Jin, Jian-Yun Nie, Zhiwei Shi, Ben He
Venue: CIKM
Year: 2011

User generated social annotations provide extra information for describing document contents. In this paper, we propose an effective method to model the categorization property of social annotations and explore the potential of combining it with classical language models for improving retrieval performance. Specifically, a novel TR-LDA model is presented to take annotations as an additional source for generating document contents apart from the document itself. We provide strategies for representing and weighting the categorization property and develop an efficient inference algorithm, where space saving is taken into account. Experiments are carried out on synthetic datasets, where documents and queries come from the standard evaluation conference TREC and annotations come from the website Delicious.com. Our results demonstrate the effectiveness of the proposed method on the ad-hoc retrieval task, which significantly outperforms state-of-art baselines.
Continuous data stream query in the cloud
Authors: Jun Li, Peng Zhang, Jianlong Tan, Ping Liu, Li Guo
Venue: CIKM
Year: 2011

Cloud computing represents one of the most important research directions for modern computing systems. Existing research efforts on Cloud computing were all focused on designing advanced storage and query techniques for static data. None of them consider the problem that data in a Cloud may appear as continuous and rapid data streams. To address this problem, in this paper we propose a new LCN-Index framework to handle continuous data stream queries in the Cloud. LCN-Index uses the Map-Reduce computing paradigm to process all the queries. In the Mapping stage, it divides all the queries into a batch of predicate sets which are then deployed onto mapping nodes using interval predicate index. In the reducing stage, it merges results from the mapping nodes using multi attribute hash index. In so doing, a data stream can be efficiently evaluated by traversing through the LCN-Index framework. Experiments demonstrate the utility of the proposed method.
Imbalanced sentiment classification
Authors: Shoushan Li, Guodong Zhou, Zhongqing Wang, Sophia Yat Mei Lee, Rangyang Wang
Venue: CIKM
Year: 2011

Sentiment classification has undergone significant development in recent years. However, most existing studies assume the balance between negative and positive samples, which may not be true in reality. In this paper, we investigate imbalanced sentiment classification instead. In particular, a novel clustering-based stratified under-sampling framework and a centroid-directed smoothing strategy are proposed to address the imbalanced class and feature distribution problems respectively. Evaluation across different datasets shows the effectiveness of both the under-sampling framework and the smoothing strategy in handling the imbalanced problems in real sentiment classification applications.
Cost-efficient repair in inconsistent probabilistic databases
Authors: Xiang Lian, Yincheng Lin, Lei Chen
Venue: CIKM
Year: 2011

Due to the ubiquitous data uncertainty in many emerging real applications, efficient management of probabilistic databases has become an increasingly important yet challenging problem. In particular, one fundamental task of data management is to identify those unreliable data in the probabilistic database that violate integrity constraints (e.g., functional dependencies), and then quickly resolve data inconsistencies. In this paper, we formulate and tackle an important problem of repairing inconsistent probabilistic databases efficiently by value modification. Specifically, we propose a repair semantic, namely possible-world-oriented repair (PW-repair), which partitions possible worlds into several disjoint groups, and repairs these groups individually with minimum repair costs. Due to the intractable result that finding such a PW-repair strategy is NP-complete, we carefully design a heuristic-based greedy approach for PW-repair, which can efficiently obtain an effective repair of the inconsistent probabilistic database. Through extensive experiments, we show that our approach can achieve the efficiency and effectiveness of the repair on inconsistent probabilistic data.