OpenRaiser/Intern-Atlas huggingface dataset:
Simulating simple user behavior for system effectiveness evaluation
Authors: Ben Carterette, Evangelos Kanoulas, Emine Yilmaz
Venue: CIKM
Year: 2011

Information retrieval effectiveness evaluation typically takes one of two forms: batch experiments based on static test collections, or lab studies measuring actual users interacting with a system. Test collection experiments are sometimes viewed as introducing too many simplifying assumptions to accurately predict the usefulness of a system to its users. As a result, there is great interest in creating test collections and measures that better model user behavior. One line of research involves developing measures that include a parameterized user model; choosing a parameter value simulates a particular type of user. We propose that these measures offer an opportunity to more accurately simulate the variance due to user behavior, and thus to analyze system effectiveness to a simulated user population. We introduce a Bayesian procedure for producing sampling distributions from click data, and show how to use statistical tools to quantify the effects of variance due to parameter selection.
Efficiency optimizations for interpolating subqueries
Authors: Marc-Allen Cartright, James Allan
Venue: CIKM
Year: 2011

A large class of queries can be viewed as linear combinations of smaller subqueries. Additionally, many situations arise when part or all of one subquery has been preprocessed or has cached information, while another subquery requires full processing. This type of query is common, for example, in relevance feedback settings where the original query has been run to produce a set of expansion terms, but the expansion terms still need to be processed. We investigate mechanisms to reduce the time needed to process queries of this nature. We use RM3, a variant of the Relevance Model scoring algorithm, as our instantiation of this arrangement. We examine the different scenarios that can arise when we have access to the internal structure of each subquery. Given this additional information, we investigate methods to utilize this information, reducing processing costs substantially. Depending on the amount of accessibility we have into the subqueries, we can reduce processing costs over 80% without affecting the score of the final results.
Finding information nebula over large networks
Authors: Lijun Chang, Jeffrey Xu Yu, Lu Qin, Yuanyuan Zhu, Haixun Wang
Venue: CIKM
Year: 2011

Social and information networks have been extensively studied over years. In this paper, we concentrate ourselves on a large information network that is composed of entities and relationships, where entities are associated with sets of keyword terms (kterms) to specify what they are, and relationships describe the link structure among entities which can be very complex. Our work is motivated but is different from the existing works that find a best subgraph to describe how user-specified entities are connected. We compute information nebula (cloud) which is a set of top-K kterms P that are most correlated to a set of user-specified kterms Q, over a large information network. Our goal is to find how kterms are correlated given the complex information network among entities. The information nebula computing requests us to take all possible kterms into consideration for the top-K kterms selection, and needs to measure the similarity between kterms by considering all possible subgraphs that connect them instead of the best single one. In this work, we compute information nebula using a global structural-context similarity, and our similarity measure is independent of connection subgraphs. To the best of our knowledge, among the link-based similarity methods, none of the existing work considers similarity between two sets of nodes or two kterms. We propose new algorithms to find top-K kterms P for a given set of kterms Q based on the global structural-context similarity, without computing all the similarity scores of kterms in the large information network. We performed extensive performance studies using large real datasets, and confirmed the effectiveness and efficiency of our approach.
Coupling or decoupling for KNN search on road networks?: a hybrid framework on user query patterns
Authors: Ying-Ju Chen, Kun-Ta Chuang, Ming-Syan Chen
Venue: CIKM
Year: 2011

We explore in this paper a new KNN algorithm, called the SQUARE algorithm, for searching spatial objects on road networks. Recent works in the literature discussed the necessity to support object updates for promising location-based services. Among them, the decoupling spatial search algorithms, which separate the handle of the network traversal and the object lookup, has been recognized as the most effective approach to cut the maintenance overhead from updates. However, the queue-based network traversal needs to be performed from scratch for each KNN query until the KNN objects are exactly identified, indicating that the query complexity is in proportion to the number of visited network nodes. The query efficiency is concerned for online LBS applications since they only allow lightweight operations for minimizing the query latency. To improve the query scalability while supporting data updates, SQUARE constructs the network index similar to the way used in decoupling models, and meanwhile exploit the coupling idea to maintain the KNN information relative to hot regions in the network index. The hot region denotes the area with frequent queries discovered in the query history. Inspired from the prevalently observed 80-20 rule, SQUARE can maximize the query throughput by returning KNN results in the quasi-constant time for 80% queries that are roughly issued within 20% area (hot regions). As validated in our experimental results, SQUARE outperforms previous works and achieves the significant performance improvement without sacrifice on the maintenance overhead for object updates.
Perspective hierarchical dirichlet process for user-tagged image modeling
Authors: Xin Chen, Xiaohua Hu, Yuan An, Zunyan Xiong, Tingting He, E. K. Park
Venue: CIKM
Year: 2011

In this paper, we proposed a perspective Hierarchical Dirichlet Process (pHDP) model to deal with user-tagged image modeling. The contribution is two-fold. Firstly, we associate image features with image tags. Secondly, we incorporate the user's perspectives into the image tag generation process and introduce new latent variables to determine if an image tag is generated from user's perspectives or from the image content. Therefore, the model is able to extract both embedded semantic components and user's perspectives from user-tagged images. Based on the proposed pHDP model, we achieve automatic image tagging with users' perspective. Experimental results show that the pHDP model achieves better image tagging performance compared to state-of-the-art topic models.
Improving context-aware query classification via adaptive self-training
Authors: Minmin Chen, Jian-Tao Sun, Xiaochuan Ni, Yixin Chen
Venue: CIKM
Year: 2011

Topical classification of user queries is critical for general-purpose web search systems. It is also a challenging task, due to the sparsity of query terms and the lack of labeled queries. On the other hand, search contexts embedded in query sessions and unlabeled queries free on the web have not been fully utilized in most query classification systems. In this work, we leverage these information to improve query classification accuracy.
Continuously monitoring the correlations of massive discrete streams
Authors: Yueguo Chen, Wei Wang, Xiaoyong Du, Xiaofang Zhou
Venue: CIKM
Year: 2011

The problem of monitoring the correlations of discrete streams is to continuously monitor the temporal correlations among massive discrete streams. A temporal correlation of two streams is defined as a tracking behavior, i.e., the most recent pattern of one stream is very similar to a historical pattern of another stream. The challenge is that both the tracking stream and the tracked stream are evolving, which causes the frequent updates of the correlation-ships. The straightforward way of monitoring correlations by brute-force subsequence matching will be very expensive for massive streams. We propose techniques that are able to significantly reduce the number of expensive subsequence matching calls, by continuously pruning and refining the correlated streams. Extensive experiments on the streaming trajectories show the significant performance improvement achieved by the proposed algorithms.
Automated feature generation from structured knowledge
Authors: Weiwei Cheng, Gjergji Kasneci, Thore Graepel, David H. Stern, Ralf Herbrich
Venue: CIKM
Year: 2011

The prediction accuracy of any learning algorithm highly depends on the quality of the selected features; but often, the task of feature construction and selection is tedious and nonscalable. In recent years, however, there have been numerous projects with the goal of constructing general-purpose or domain-specific knowledge bases with entity-relationship-entity triples extracted from various Web sources or collected from user communities, e.g. YAGO, DBpedia, Freebase, UMLS, etc. This paper advocates the simple and yet far-reaching idea that the structured knowledge contained in such knowledge bases can be exploited to automatically extract features for general learning tasks. We introduce an expressive graph-based language for extracting features from such knowledge bases and a theoretical framework for constructing feature vectors from the extracted features. Our experimental evaluation on different learning scenarios provides evidence that the features derived through our framework can considerably improve the prediction accuracy, especially when the labeled data at hand is sparse.
An algorithm for axiom pinpointing in EL+ and its incremental variant
Authors: Xiaojun Cheng, Guilin Qi
Venue: CIKM
Year: 2011

Axiom pinpointing plays an important role in the development and maintenance of ontologies. It helps the user to comprehend an unwanted entailment of an ontology by presenting all minimal subsets of the ontology which are responsible for the entailment (called MinAs). In this paper, we consider the problem of axiom pinpointing in description logic EL+, which underpins OWL 2 EL, a profile of the latest version of Web Ontology Language (OWL). We propose a novel method to compute all MinAs that utilizes the hierarchy information obtained from the classification of an EL+ ontology. The advantage of our method over an existing labeled classification based method is that we do not attach labels to entailed subsumptions, which can be memory exhaustion for large scale ontologies. We further consider axiom pinpointing in EL+ when ontologies change. An incremental algorithm is given to compute all MinAs by reusing MinAs previously computed.
Tractable XML data exchange via relations
Authors: Rada Chirkova, Leonid Libkin, Juan L. Reutter
Venue: CIKM
Year: 2011

We consider data exchange for XML documents: given source and target schemas, a mapping between them, and a document conforming to the source schema, construct a target document and answer target queries in a way that is consistent with source information. The problem has primarily been studied in the relational context, in which data-exchange systems have also been built. Since many XML documents are stored in relations, it is natural to consider using a relational system for XML data exchange. However, there is a complexity mismatch between query answering in relational and XML data exchange, which indicates that restrictions have to be imposed on XML schemas and mappings, and on XML shredding schemes, to make the use of relational systems possible. We isolate a set of five requirements that must be fulfilled in order to have a faithful representation of the XML data-exchange problem by a relational translation. We then demonstrate that these requirements naturally suggest the inlining technique for dataexchange tasks. Our key contribution is to provide shredding algorithms for schemas, documents, mappings and queries, and demonstrate that they enable us to correctly perform XML data-exchange tasks using a relational system.
Text vs. space: efficient geo-search query processing
Authors: Maria Christoforaki, Jinru He, Constantinos Dimopoulos, Alexander Markowetz, Torsten Suel
Venue: CIKM
Year: 2011

Many web search services allow users to constrain text queries to a geographic location (e.g., yoga classes near Santa Monica). Important examples include local search engines such as Google Local and location-based search services for smart phones. Several research groups have studied the efficient execution of queries mixing text and geography; their approaches usually combine inverted lists with a spatial access method such as an R-tree or space-filling curve. In this paper, we take a fresh look at this problem. We feel that previous work has often focused on the spatial aspect at the expense of performance considerations in text processing, such as inverted index access, compression, and caching. We describe new and existing approaches and discuss their different perspectives. We then compare their performance in extensive experiments on large document collections. Our results indicate that a query processor that combines state-of-the-art text processing techniques with a simple coarse-grained spatial structure can outperform existing approaches by up to two orders of magnitude. In fact, even a naive approach that first uses a simple inverted index and then filters out any documents outside the query range outperforms many previous methods.
I/O-efficient algorithms for answering pattern-based aggregate queries in a sequence OLAP system
Authors: Chun Kit Chui, Ben Kao, Eric Lo, Reynold Cheng
Venue: CIKM
Year: 2011

Many kinds of real-life data exhibit logical ordering among their data items and are thus sequential in nature. In recent years, the concept of Sequence OLAP (S-OLAP) has been proposed. The biggest distinguishing feature of SOLAP from traditional OLAP is that data sequences managed by an S-OLAP system are characterized by the subsequence/substring patterns they possess. An S-OLAP system thus supports pattern-based grouping and aggregation. Conceptually, an S-OLAP system maintains a sequence data cube which is composed of sequence cuboids. Each sequence cuboid presents the answer of a pattern-based aggregate (PBA) query. This paper focuses on the I/O aspects of evaluating PBA queries. We study the problems of joining plan selection and execution planning, which are the core issues in the design of I/O-efficient cuboid materialization algorithms. Through an empirical study, we show that our algorithms lead to a very I/O-efficient strategy for sequence cuboid materialization.
Indexes for highly repetitive document collections
Authors: Francisco Claude, Antonio Fariña, Miguel A. Martínez-Prieto, Gonzalo Navarro
Venue: CIKM
Year: 2011

We introduce new compressed inverted indexes for highly repetitive document collections. They are based on run-length, Lempel-Ziv, or grammar-based compression of the differential inverted lists, instead of gap-encoding them as is the usual practice. We show that our compression methods significantly reduce the space achieved by classical compression, at the price of moderate slowdowns. Moreover, many of our methods are universal, that is, they do not need to know the versioning structure of the collection.
Practical representations for web and social graphs
Authors: Francisco Claude, Susana Ladra
Venue: CIKM
Year: 2011

In this paper we focus on representing Web and social graphs. Our work is motivated by the need of mining information out of these graphs, thus our representations do not only aim at compressing the graphs, but also at supporting efficient navigation. This allows us to process bigger graphs in main memory, avoiding the slowdown brought by resorting on external memory. We first show how by just partitioning the graph and combining two existing techniques for Web graph compression, k2-trees [Brisaboa, Ladra and Navarro, SPIRE 2009] and RePair-Graph [Claude and Navarro, TWEB 2010], exploiting the fact that most links are intra-domain, we obtain the best time/space trade-off for direct and reverse navigation when compared to the state of the art. In social networks, splitting the graph to achieve a good decomposition is not easy. For this case, we explore a new proposal for indexing MPK linearizations [Maserrat and Pei, KDD 2010], which have proven to be an effective way of representing social networks in little space by exploiting common dense subgraphs. Our proposal offers better worst case bounds in space and time, and is also a competitive alternative in practice.
Learning to rank results in relational keyword search
Authors: Joel Coffman, Alfred C. Weaver
Venue: CIKM
Year: 2011

Keyword search within databases has become a hot topic within the research community as databases store increasing amounts of information. Users require an effective method to retrieve information from these databases without learning complex query languages (viz. SQL). Despite the recent research interest, performance and search effectiveness have not received equal attention, and scoring functions in particular have become increasingly complex while providing only modest benefits with regards to the quality of search results. An analysis of the factors appearing in existing scoring functions suggests that some factors previously deemed critical to search effectiveness are at best loosely correlated with relevance. We consider a number of these different scoring factors and use machine learning to create a new scoring function that provides significantly better results than existing approaches. We simplify our scoring function by systematically removing the factors with the lowest weight and show that this version still outperforms the previous state-of-the-art in this area.
Image clustering fusion technique based on BFS
Authors: Luca Costantini, Raffaele Nicolussi
Venue: CIKM
Year: 2011

With the increasing in number and size of databases dedicated to the storage of visual content, the need for effective retrieval systems has become crucial. The proposed method makes a significant contribution to meet this need through a technique in which sets of clusters are fused together to create an unique and more significant set of clusters. The images are represented by some features and then are grouped by these features, that are considered one by one. A probability matrix is then built and explored by the breadth first search algorithm with the aim of select an unique set of clusters. Experimental results, obtained using two different datasets, show the effectiveness of the proposed technique. Furthermore, the proposed approach overcomes the drawback of tuning a set of parameters that fuse the similarity measurement obtained by each feature to get an overall similarity between two images.
Multi-view random walk framework for search task discovery from click-through log
Authors: Jianwei Cui, Hongyan Liu, Jun Yan, Lei Ji, Ruoming Jin, Jun He, Yingqin Gu, Zheng Chen, Xiaoyong Du
Venue: CIKM
Year: 2011

Search engine users often have clear search tasks hidden behind their queries. Inspired by this, the modern search engines are providing an increasing number of services to help users simplify their key tasks. However, the problem of what are the major user search tasks with high traffic for which search engines should design special services is still underexplored. In this paper, we propose a novel Multi-view Random Walk (MRW) algorithm to measure the search task oriented similarity between queries, and then group search queries with similar tasks so that the major search tasks of users can be identified from search engine click-through log. The proposed MRW, which is a general framework to combine knowledge from different views in a random walk process, allows the random surfer to walk across different views to integrate information for search task discovery. Experimental results on click-through log of a commonly used commercial search engine show that our proposed MRW algorithm can effectively discover user search tasks.
DOLAP 2011: overview of the 14th international workshop on data warehousing and olap
Authors: Alfredo Cuzzocrea, Karen C. Davis, Il-Yeol Song
Venue: CIKM
Year: 2011

The ACM 14th International Workshop on Data Warehousing and OLAP (DOLAP 2011), held in Glasgow, Scotland, UK on October 28, 2011, in conjunction with the ACM 20th International Conference on Information and Knowledge Management (CIKM 2011), presents research on data warehousing and On-Line Analytical Processing (OLAP). The DOLAP 2011 program has three interesting sessions on data warehouse modeling and maintenance, ETL and performance, and OLAP visualization and extensions, and a panel discussing analytics in data warehouses.
An integrated environment for semantic knowledge work
Authors: Aba-Sah Dadzie, Victoria S. Uren, Ziqi Zhang, Philip Webster
Venue: CIKM
Year: 2011

In this demonstration, we will present a semantic environment called the K-Box. The K-Box supports the lightweight integration of knowledge tools, with a focus on semantic tools, but with the flexibility to integrate natural language and conventional tools. We discuss the implementation of the framework, and two existing applications, including details of a new application for developers of semantic workflows. The demonstration will be of interest to developers and researchers of ontology-based knowledge management systems, and semantic desktops, and to analysts working with cross-media information.
Using virtual documents to move information retrieval and knowledge management closer together
Authors: Danica Damljanovic, Udo Kruschwitz, M-Dyaa Albakour
Venue: CIKM
Year: 2011

While Information Retrieval approaches typically rely on a bag-of-word approach and are therefore fairly shallow, Knowledge Management is based on a deep semantic representation. Both allow users to sift through huge volumes of information and to identify the relevant document or answer for a particular information need. Obviously, these areas go beyond this simple information access scenario. Nevertheless, it is also a fact that these areas form fairly separate communities. We propose an idea of how to make use of techniques coming from both ends of the spectrum and combine them in methods that are more powerful than each of them individually. Our idea is based on turning structured information into virtual documents built to preserve the concepts and relations inherent in the semantically rich data before we apply Information Retrieval methods.
Inferring query aspects from reformulations using clustering
Authors: Van Dang, Xiaobing Xue, W. Bruce Croft
Venue: CIKM
Year: 2011

When the information need is not clear from the user query, a good strategy would be to return documents that cover as many aspects of the query as possible. To do this, the possible aspects of the query need to be automatically identified. In this paper, we propose to do this by clustering reformulated queries generated from publicly available resources and using each cluster to represent an aspect of the query. Our results show that the automatically generated reformulations for the TREC Web Track queries match up quite well with actual sub-topics of these queries identified by TREC experts. Moreover, agglomerative clustering using query-to-query similarity based on co-occurrence in text passages can provide clusters of high quality that potentially can be used to identify aspects.