OpenRaiser/Intern-Atlas huggingface dataset:
Memory-less unsupervised clustering for data streaming by versatile ellipsoidal function
Authors: Niwan Wattanakitrungroj, Chidchanok Lursinsap
Venue: CIKM
Year: 2011

The challenge of clustering on data stream is the ability to deal with the continuous incoming data which are unlimited and unable to store all of them. To manage the storage crisis, the data must be processed in a single pass or only once after the arrival and are thrown away outer. All previously clustered data must be mathematically captured in terms of group features since those data are already non-existent. The proposed data stream clustering algorithm is divided into two main phases, namely on-line and off-line. In the on-line phase, new micro-cluster features are proposed. Our micro-cluster features better represent the arriving data than the traditional micro-cluster features. In the off-line phase, the prepared micro-clusters are categorized by their densities. The proposed method can generate the final clusters with different shapes and densities. Based on entropy, purity, Jaccard coefficient, and Rand statistic measures, our algorithm being applied on synthetic and real data outperforms the other previous data stream clustering algorithms.
Using games with a purpose and bootstrapping to create domain-specific sentiment lexicons
Authors: Albert Weichselbraun, Stefan Gindl, Arno Scharl
Venue: CIKM
Year: 2011

Sentiment detection analyzes the positive or negative polarity of text. The field has received considerable attention in recent years, since it plays an important role in providing means to assess user opinions regarding an organization's products, services, or actions. Approaches towards sentiment detection include machine learning techniques as well as computationally less expensive methods. Both approaches rely on the use of language-specific sentiment lexicons, which are lists of sentiment terms with their corresponding sentiment value. The effort involved in creating, customizing, and extending sentiment lexicons is considerable, particularly if less common languages and domains are targeted without access to appropriate language resources. This paper proposes a semi-automatic approach for the creation of sentiment lexicons which assigns sentiment values to sentiment terms via crowd-sourcing. Furthermore, it introduces a bootstrapping process operating on unlabeled domain documents to extend the created lexicons, and to customize them according to the particular use case. This process considers sentiment terms as well as sentiment indicators occurring in the discourse surrounding a articular topic. Such indicators are associated with a positive or negative context in a particular domain, but might have a neutral connotation in other domains. A formal evaluation shows that bootstrapping considerably improves the method's recall. Automatically created lexicons yield a performance comparable to professionally created language resources such as the General Inquirer.
Authormagic: an approach to author disambiguation in large-scale digital libraries
Authors: Henning Weiler, Klaus Meyer-Wegener, Salvatore Mele
Venue: CIKM
Year: 2011

A collaboration of leading research centers in the field of High Energy Physics (HEP) has built INSPIRE, a novel information infrastructure, which comprises the entire corpus of about one million documents produced within the discipline, including a rich set of metadata, citation information and half a million full-text documents, and offers a unique opportunity for author disambiguation strategies. The presented approach features extended metadata comparison metrics and a three-step unsupervised graph clustering technique. The algorithm aided in identifying 200'000 individuals from 6'500'000 author signatures. Preliminary tests based on knowledge of external experts and a pilot of a crowd-sourcing system show a success rate of more than 96% within the selected test cases. The obtained author clusters serve as a recommendation for INSPIRE users to further clean the publication list in a crowd-sourced approach.
Improving user interest inference from social neighbors
Authors: Zhen Wen, Ching-Yung Lin
Venue: CIKM
Year: 2011

Prior research has provided some evidence of social correlation (i.e., "you are who you know"), which makes it possible to infer one's interests from his or her social neighbors. However, it is also shown to be challenging to consistently obtain high quality inference. This challenge can be partially attributed to the fact that people usually maintain diverse social relationships, in order to tap into diverse information and knowledge. It is unlikely that a person would possess all interests of his/her social neighbors. Instead, s/he may selectively acquire just a subset of them. This paper intends to improve inferring interests from neighbors given this observation. We conduct this study by implementing a privacy-preserving large distributed social sensor system in a large global IT company to capture the multifaceted activities (e.g., emails, instant messaging, social bookmarking, etc.) of 25K+ people. These activities occupy the majority of employees' time, and thus, provide a higher quality view of the diverse aspects of their professional interests compared to the friending activity on online social networking sites. In this paper, we propose a technique that exploits the correlation among the attributes that a person possesses to improve social-correlation-based inference quality. Our technique offers two unique contributions. First, we demonstrate that the proposed technique can significantly improve inference quality by as much as 76.1%. Second, we study the interaction between the two factors: social correlation and attribute correlation under different situations. The results can inform practical applications how the inference quality would change in various scenarios.
Efficient retrieval of 3D building models using embeddings of attributed subgraphs
Authors: Raoul Wessel, Sebastian Ochmann, Richard Vock, Ina Blümel, Reinhard Klein
Venue: CIKM
Year: 2011

We present a novel method for retrieval and classification of 3D building models that is tailored to the specific requirements of architects. In contrast to common approaches our algorithm relies on the interior spatial arrangement of rooms instead of exterior geometric shape. We first represent the internal topological building structure by a Room Connectivity Graph (RCG). To enable fast and efficient retrieval and classification with RCGs, we transform the structured graph representation into a vector-based one by introducing a new concept of subgraph embeddings. We provide comprehensive experiments showing that the introduced subgraph embeddings yield superior performance compared to state-of-the-art graph retrieval approaches.
Health conversational system based on contextual matching of community-driven question-answer pairs
Authors: Wilson Wong, John Thangarajah, Lin Padgham
Venue: CIKM
Year: 2011

More and more people are turning to the World Wide Web for learning and sharing information about their health using search engines, forums and question answering systems. In this demonstration, we look at a new way of delivering health information to the end-users via coherent conversations. The proposed conversational system allows the end-users to vaguely express and gradually refine their information needs using only natural language questions or statements as input. We provide example scenarios in this demonstration to illustrate the inadequacies of current delivery mechanisms and highlight the innovative aspects of the proposed conversational system.
Finding all justifications of OWL entailments using TMS and MapReduce
Authors: Gang Wu, Guilin Qi, Jianfeng Du
Venue: CIKM
Year: 2011

Finding all justifications of an OWL entailment is an important reasoning service for explaining logical inconsistencies. In this paper, we consider finding all justifications of an entailment in OWL pD* fragment, which is a fragment of OWL that makes possible decidable rule extensions of OWL. We first propose a novel approach to find all justifications of OWL pD* entailments using TMS and show the complexity of this approach. This approach is limited by the hardware capabilities of standalone systems. In order to improve its scalability to handle large scale semantic data, we optimize the proposed approach by exploiting the MapReduce technology. We implement our approach and the optimization, and do experiments on synthetic and real world data sets. Evaluation results show that our approach has the ability to scale to more than one billion triples.
CP-index: on the efficient indexing of large graphs
Authors: Yan Xie, Philip S. Yu
Venue: CIKM
Year: 2011

Graph search, i.e., finding all graphs in a database D that contain the query graph q, is a classical primitive prevalent in various graph database applications. In the past, there has been an abundance of studies devoting to this topic; however, with the recent emergence of large information networks, it places new challenges to the research community. Most of the traditional graph search schemes utilize the strategy of graph feature based indexing, whereas the index construction step that often involves frequent subgraph mining becomes a bottleneck for large graphs due to the high computational complexity. Although there have been several methods proposed to solve this mining bottleneck such as summarization of database graphs, the frequent subgraphs thus generated as indexing features are still unsatisfactory because the feature set is in general not only inadequate or deficient for the large graph scenario, but also with many redundant features. Furthermore, the large size of the graphs makes it too easy for a small feature to be contained in many of them, severely impacting its selectivity and pruning power. Motivated by all the above issues we identify, in this paper we propose a novel CP-Index (Contact Preservation) for efficient indexing of large graphs. To overcome the low selectivity issue, we reap further pruning opportunities by leveraging each feature's location information in the database graphs. Specifically, we look at how features are touching upon each other in the query, and check whether this contact pattern is preserved in the target graphs. Then, to tackle the deficiency and redundancy problems associated with features, new feature generation and selection methods such as dual feature generation and size-increasing bootstrapping feature selection are introduced to complete our design. Experiment results show that CP-Index is much more effective in indexing large graphs.
On bias problem in relevance feedback
Authors: Qianli Xing, Yi Zhang, Lanbo Zhang
Venue: CIKM
Year: 2011

Relevance feedback is an effective approach to improve retrieval quality over the initial query. Typical relevance feedback methods usually select top-ranked documents for relevance judgments, then query expansion or model updating are carried out based on the feedback documents. However, the number of feedback documents is usually limited due to expensive human labeling. Thus relevant documents in the feedback set are hardly representative of all relevant documents and the feedback set is actually biased. As a result, the performance of relevance feedback will get hurt. In this paper, we first show how and where the bias problem exists through experiments. Then we study how the bias can be reduced by utilizing the unlabeled documents. After analyzing the usefulness of a document to relevance feedback, we propose an approach that extends the feedback set with carefully selected unlabeled documents by heuristics. Our experiment results show that the extended feedback set has less bias than the original feedback set and better performance can be achieved when the extended feedback set is used for relevance feedback.
Retrieving and ranking unannotated images through collaboratively mining online search results
Authors: Songhua Xu, Hao Jiang, Francis Chi-Moon Lau
Venue: CIKM
Year: 2011

We present a new image search and ranking algorithm for retrieving unannotated images by collaboratively mining online search results which consist of online image and text search results. The online image search results are leveraged as reference examples to perform content-based image search over unannotated images. The online text search results are utilized to estimate the reference images' relevance to the search query. The key feature of our method is its capability to deal with unreliable online image search results through jointly mining visual and textual aspects of online search results. Through such collaborative mining, our algorithm infers the relevance of an online search result image to a text query. Once we obtain the estimate of query relevance score for each online image search result, we can selectively use query specific online search result images as reference examples for retrieving and ranking unannotated images. We tested our algorithm both on the standard public image datasets and several modestly sized personal photo collections. We also compared our method with two well-known peer methods. The results indicate that our algorithm is superior to existing content-based image search algorithms for retrieving and ranking unannotated images.
TAKES: a fast method to select features in the kernel space
Authors: Ye Xu, Furao Shen, Wei Ping, Jinxi Zhao
Venue: CIKM
Year: 2011

Feature selection is an effective tool to deal with the "curse of dimensionality". To cope with the non-separable problem, feature selection in the kernel space has been investigated. However, previous study cannot adequately estimate the intrinsic dimensionality of the kernel space. Thus, it is difficult to accurately preserve the sketch of the kernel space using the learned basis, and the feature selection performance is affected. Moreover, the computing load of the algorithm reaches at least cubic with the number of training data. In this paper, we propose a fast framework to conduct feature selection in the kernel space. By designing a fast kernel subspace learning method, we automatically learn the intrinsic dimensionality and construct an orthogonal basis set of kernel space. The learned basis can accurately preserve the sketch of kernel space. Then backed by the constructed basis, we directly select features in kernel space. The whole proposed framework has a quadratic complexity with the number of training data, which is faster than existing kernel methods for feature selection. We evaluate our work under several typical datasets and find it not only preserves the sketch of the kernel space more accurately but also achieves better classification performance compared with many state-of-the-art methods.
Answering label-constraint reachability in large graphs
Authors: Kun Xu, Lei Zou, Jeffrey Xu Yu, Lei Chen, Yanghua Xiao, Dongyan Zhao
Venue: CIKM
Year: 2011

In this paper, we study a variant of reachability queries, called label-constraint reachability (LCR) queries, specifically,given a label set S and two vertices u1 and u2 in a large directed graph G, we verify whether there exists a path from u1 to u2 under label constraint S. Like traditional reachability queries, LCR queries are very useful, such as pathway finding in biological networks, inferring over RDF (resource description f ramework) graphs, relationship finding in social networks. However, LCR queries are much more complicated than their traditional counterpart.Several techniques are proposed in this paper to minimize the search space in computing path-label transitive closure. Furthermore, we demonstrate the superiority of our method by extensive experiments.
Utility-driven anonymization in data publishing
Authors: Mingqiang Xue, Panagiotis Karras, Chedy Raïssi, Hung Keng Pung
Venue: CIKM
Year: 2011

Privacy-preserving data publication has been studied intensely in the past years. Still, all existing approaches transform data values by random perturbation or generalization. In this paper, we introduce a radically different data anonymization methodology. Our proposal aims to maintain a certain amount of patterns, defined in terms of a set of properties of interest that hold for the original data. Such properties are represented as linear relationships among data points. We present an algorithm that generates a set of anonymized data that strictly preserves these properties, thus maintaining specified patterns in the data. Extensive experiments with real and synthetic data show that our algorithm is efficient, and produces anonymized data that affords high utility in several data analysis tasks while safeguarding privacy.
Topic modeling for named entity queries
Authors: Xiaobing Xue, Xiaoxin Yin
Venue: CIKM
Year: 2011

Named entities are observed in a large portion of web search queries (named entity queries), where each entity can be associated with many different query terms that refer to various aspects of this entity. Organizing these query terms into topics helps understand major search intents about entities and the discovered topics are useful for applications such as query suggestion. Furthermore, we notice that named entities can often be organized into categories and those from the same category share many generic topics. Therefore, working on a category of named entities instead of individual ones helps avoid the problems caused by the sparsity and noise in the data. In this paper, Named Entity Topic Model (NETM) is proposed to discover generic topics for a category of named entities, where the quality of the generic topics is improved through the model design and the parameter initialization. Experiments based on query log data show that NETM discovers high-quality topics and outperforms the state-of-the-art techniques by 12.8% based on F1 measure.
Partial duplicate detection for large book collections
Authors: Ismet Zeki Yalniz, Ethem F. Can, R. Manmatha
Venue: CIKM
Year: 2011

A framework is presented for discovering partial duplicates in large collections of scanned books with optical character recognition (OCR) errors. Each book in the collection is represented by the sequence of words (in the order they appear in the text) which appear only once in the book. These words are referred to as "unique words" and they constitute a small percentage of all the words in a typical book. Along with the order information the set of unique words provides a compact representation which is highly descriptive of the content and the flow of ideas in the book. By aligning the sequence of unique words from two books using the longest common subsequence (LCS) one can discover whether two books are duplicates. Experiments on several datasets show that DUPNIQ is more accurate than traditional methods for duplicate detection such as shingling and is fast. On a collection of 100K scanned English books DUPNIQ detects partial duplicates in 30 min using 350 cores and has precision 0.996 and recall 0.833 compared to shingling with precision 0.992 and recall 0.720. The technique works on other languages as well and is demonstrated for a French dataset.
RerankEverything: a reranking interface for exploring search results
Authors: Takehiro Yamamoto, Satoshi Nakamura, Katsumi Tanaka
Venue: CIKM
Year: 2011

This paper proposes a system called "RerankEverything", which enables users to rerank search results in any search service, such as a Web search engine, an e-commerce site, a hotel reservation site, and so on. This system helps users explore diverse search results. In conventional search services, interactions between users and systems are quite limited and complicated. By using RerankEverything, users can interactively explore search results in accordance with their interests by reranking search results from various viewpoints. Experimental results show that our system potentially help users search more proactively. When using our system, users were more likely to click search results that were initially low ranked. Users also browsed through more diverse search results by reranking search results after giving various types of feedback with our system.
Extracting adjective facets from community Q&A corpus
Authors: Takehiro Yamamoto, Satoshi Nakamura, Katsumi Tanaka
Venue: CIKM
Year: 2011

In this paper, we propose a method for helping users explore information via Web searches by using a question and answer (Q&A) corpus archived in a community Q&A site. When users do not have clear information needs and have little knowledge about the task domain, it is difficult for them to create queries that adequately reflect their information needs. We focused on terms like "famous temples," "historical townscapes," and "delicious sweets," which we call "adjective facets", and developed a method of extracting these facets from question and answer archives at a community Q&A site. We evaluated the effectiveness of our adjective facets by comparing them with several baselines.
Context-aware query recommendation by learning high-order relation in query logs
Authors: Xiaohui Yan, Jiafeng Guo, Xueqi Cheng
Venue: CIKM
Year: 2011

Query recommendation has been widely used in modern search engines. Recently, several context-aware methods have been proposed to improve the accuracy of recommendation by mining query sequence patterns from query sessions. However, the existing methods usually do not address the ambiguity of queries explicitly and often suffer from the sparsity of the training data. In this paper, we propose a novel context-aware query recommendation approach by modeling the high-order relation between queries and clicks in query log, which captures users' latent search intents. Empirical experiment results demonstrate that our approach outperforms the baseline methods in providing high quality recommendations for ambiguous queries.
CLUES: a unified framework supporting interactive exploration of density-based clusters in streams
Authors: Di Yang, Zhenyu Guo, Elke A. Rundensteiner, Matthew O. Ward
Venue: CIKM
Year: 2011

Although various mining algorithms have been proposed in the literature to efficiently compute clusters, few strides have been made to date in helping analysts to interactively explore such patterns in the stream context. We present a framework called CLUES to both computationally and visually support the process of real-time mining of density-based clusters. CLUES is composed of three major components. First, as foundation of CLUES, we develop an evolution model of density-based clusters in data streams that captures the complete spectrum of cluster evolution types across streaming windows. Second, to equip CLUES with the capability of efficiently tracking cluster evolution, we design a novel algorithm to piggy-back the evolution tracking process into the underlying cluster detection process. Third, CLUES organizes the detected clusters and their evolution interrelationships into a multidimensional pattern space - presenting clusters at different time horizons and across different abstraction levels. It provides a rich set of visualization and interaction techniques to allow the analyst to explore this multi-dimensional pattern space in real-time. Our experimental evaluation, including performance studies and a user study, using real streams from ground group movement monitoring and from stock transaction domains confirm both the efficiency and effectiveness of our proposed CLUES framework.
Towards noise-resilient document modeling
Authors: Tao Yang, Dongwon Lee
Venue: CIKM
Year: 2011

We introduce a generative probabilistic document model based on latent Dirichlet allocation (LDA), to deal with textual errors in the document collection. Our model is inspired by the fact that most large-scale text data are machine-generated and thus inevitably contain many types of noise. The new model, termed as TE-LDA, is developed from the traditional LDA by adding a switch variable into the term generation process in order to tackle the issue of noisy text data. Through extensive experiments, the efficacy of our proposed model is validated using both real and synthetic data sets.