OpenRaiser/Intern-Atlas huggingface dataset:
A new tool for multi-level partitioning in teradata
Authors: Young-Kyoon Suh, Ahmad Ghazal, Alain Crolotte, Pekka Kostamaa
Venue: CIKM
Year: 2012

This paper introduces a new tool that recommends an optimized partitioning solution called Multi-Level Partitioned Primary Index (MLPPI) for a fact table based on the queries in the workload. The tool implements a new technique using a greedy algorithm for search space enumeration. The space is driven by predicates in the queries. This technique fits very well the Teradata MLPPI scheme, as it is based on a general framework using general expressions, ranges and case expressions for partition definitions. The cost model implemented in the tool is based on the Teradata optimizer, and it is used to prune the search space for reaching a final solution. The tool resides completely on the client, and interfaces the database through APIs as opposed to previous work that requires optimizer code extension. The APIs are used to simplify the workload queries, and to capture fact table predicates and costs necessary to make the recommendation. The predicate-driven method implemented by the tool is general, and it can be applied to any clustering or partitioning scheme based on simple field expressions or complex SQL predicates. Experimental results given a particular workload will show that the recommendation from the tool outperforms a human expert. The experiments also show that the solution is scalable both with the workload complexity and the size of the fact table.
Active learning for relation type extension with local and global data views
Authors: Ang Sun, Ralph Grishman
Venue: CIKM
Year: 2012

Relation extraction is the process of identifying instances of specified types of semantic relations in text; relation type extension involves extending a relation extraction system to recognize a new type of relation. We present LGCo-Testing, an active learning system for relation type extension based on local and global views of relation instances. Locally, we extract features from the sentence that contains the instance. Globally, we measure the distributional similarity between instances from a 2 billion token corpus. Evaluation on the ACE 2004 corpus shows that LGCo-Testing can reduce annotation cost by 97% while maintaining the performance level of supervised learning.
Location selection for utility maximization with capacity constraints
Authors: Yu Sun, Jin Huang, Yueguo Chen, Rui Zhang, Xiaoyong Du
Venue: CIKM
Year: 2012

Given a set of client locations, a set of facility locations where each facility has a service capacity, and the assumptions that: (i) a client seeks service from its nearest facility; (ii) a facility provides service to clients in the order of their proximity, we study the problem of selecting all possible locations such that setting up a new facility with a given capacity at these locations will maximize the number of served clients. This problem has wide applications in practice, such as setting up new distribution centers for online sales business and building additional base stations for mobile subscribers. We formulate the problem as location selection query for utility maximization. After applying three pruning rules to a baseline solution,we obtain an efficient algorithm to answer the query. Extensive experiments confirm the efficiency of our proposed algorithm.
Fast multi-task learning for query spelling correction
Authors: Xu Sun, Anshumali Shrivastava, Ping Li
Venue: CIKM
Year: 2012

In this paper, we explore the use of a novel online multi-task learning framework for the task of search query spelling correction. In our procedure, correction candidates are initially generated by a ranker-based system and then re-ranked by our multi-task learning algorithm. With the proposed multi-task learning method, we are able to effectively transfer information from different and highly biased training datasets, for improving spelling correction on all datasets. Our experiments are conducted on three query spelling correction datasets including the well-known TREC benchmark dataset. The experimental results demonstrate that our proposed method considerably outperforms the existing baseline systems in terms of accuracy. Importantly, the proposed method is about one order of magnitude faster than baseline systems in terms of training speed. Compared to the commonly used online learning methods which typically require more than (e.g.,) 60 training passes, our proposed method is able to closely reach the empirical optimum in about 5 passes.
Learning to rank for hybrid recommendation
Authors: Jiankai Sun, Shuaiqiang Wang, Byron J. Gao, Jun Ma
Venue: CIKM
Year: 2012

Most existing recommender systems can be classified into two categories: collaborative filtering and content-based filtering. Hybrid recommender systems combine the advantages of the two for improved recommendation performance. Traditional recommender systems are rating-based. However, predicting ratings is an intermediate step towards their ultimate goal of generating rankings or recommendation lists. Learning to rank is an established means of predicting rankings and has recently demonstrated high promise in improving quality of recommendations. In this paper, we propose LRHR, the first attempt that adapts learning to rank to hybrid recommender systems. LRHR first defines novel representations for both users and items so that they can be content-comparable. Then, LRHR identifies a set of novel meta-level features for learning purposes. Finally, LRHR adopts RankSVM, a pairwise learning to rank algorithm, to generate recommendation lists of items for users. Extensive experiments on benchmarks in comparison with the state-of-the-art algorithms demonstrate the performance gain of our approach.
If you are happy and you know it... tweet
Authors: Amir Asiaee T., Mariano Tepper, Arindam Banerjee, Guillermo Sapiro
Venue: CIKM
Year: 2012

Extracting sentiment from Twitter data is one of the fundamental problems in social media analytics. Twitter's length constraint renders determining the positive/negative sentiment of a tweet difficult, even for a human judge. In this work we present a general framework for per-tweet (in contrast with batches of tweets) sentiment analysis which consists of: (1) extracting tweets about a desired target subject, (2) separating tweets with sentiment, and (3) setting apart positive from negative tweets. For each step, we study the performance of a number of classical and new machine learning algorithms. We also show that the intrinsic sparsity of tweets allows performing classification in a low dimensional space, via random projections, without losing accuracy. In addition, we present weighted variants of all employed algorithms, exploiting the available labeling uncertainty, which further improve classification accuracy. Finally, we show that spatially aggregating our per-tweet classification results produces a very satisfactory outcome, making our approach a good candidate for batch tweet sentiment analysis.
The framework of a people recommender based on a time series of user preferences
Authors: Kosuke Takano, Kin Fun Li
Venue: CIKM
Year: 2012

In social media, it is important to build a community that includes people who share similar interests and purposes to foster further interaction and communication. In this study, we present a user profile construction method based on a time series of user preferences to allow the recommendation of appropriate people for the community. This method extracts user preferences as time series data by capturing the user's information browsing behavior in three information spaces: (1) a Web document information space, (2) an augmented reality information space, and (3) an interaction information space with applications for mobile devices. Our proposed method suggests potential members of a clique thus providing opportunities for users of social media to notice the implicit interests associated with other users based on their browsing behavior from the past to the current state, as well as to encourage social communication and relationships.
Tweet classification based on their lifetime duration
Authors: Hikaru Takemura, Keishi Tajima
Venue: CIKM
Year: 2012

Many microblog messages remain useful only within a short time, and users often find such a message after its informational value has vanished. Users also sometimes miss old but still useful messages buried among outdated ones. To solve these problems, we develop a method of classifying messages into the following three categories: (1) messages that users should read now because their value will diminish soon, (2) messages that users may read later because their value will not largely change soon, and (3) messages that are not useful anymore because their value has vanished. Our method uses an error correcting output code consisting of binary classifiers each of which determines whether a given message has value at specific time point. Our experiments on Twitter data confirmed that it outperforms naive methods.
CloST: a hadoop-based storage system for big spatio-temporal data analytics
Authors: Haoyu Tan, Wuman Luo, Lionel M. Ni
Venue: CIKM
Year: 2012

During the past decade, various GPS-equipped devices have generated a tremendous amount of data with time and location information, which we refer to as big spatio-temporal data. In this paper, we present the design and implementation of CloST, a scalable big spatio-temporal data storage system to support data analytics using Hadoop. The main objective of CloST is to avoid scan the whole dataset when a spatio-temporal range is given. To this end, we propose a novel data model which has special treatments on three core attributes including an object id, a location and a time. Based on this data model, CloST hierarchically partitions data using all core attributes which enables efficient parallel processing of spatio-temporal range scans. According to the data characteristics, we devise a compact storage structure which reduces the storage size by an order of magnitude. In addition, we proposes scalable bulk loading algorithms capable of incrementally adding new data into the system. We conduct our experiments using a very large GPS log dataset and the results show that CloST has fast data loading speed, desirable scalability in query processing, as well as high data compression ratio.
Incorporating occupancy into frequent pattern mining for high quality pattern recommendation
Authors: Linpeng Tang, Lei Zhang, Ping Luo, Min Wang
Venue: CIKM
Year: 2012

Mining interesting patterns from transaction databases has attracted a lot of research interest for more than a decade. Most of those studies use frequency, the number of times a pattern appears in a transaction database, as the key measure for pattern interestingness. In this paper, we introduce a new measure of pattern interestingness, occupancy. The measure of occupancy is motivated by some real-world pattern recommendation applications which require that any interesting pattern X should occupy a large portion of the transactions it appears in. Namely, for any supporting transaction t of pattern X, the number of items in X should be close to the total number of items in t. In these pattern recommendation applications, patterns with higher occupancy may lead to higher recall while patterns with higher frequency lead to higher precision. With the definition of occupancy we call a pattern dominant if its occupancy is above a user-specified threshold. Then, our task is to identify the qualified patterns which are both frequent and dominant. Additionally, we also formulate the problem of mining top-k qualified patterns: finding the qualified patterns with the top-k values of any function (e.g. weighted sum of both occupancy and support).
Managing interoperability and compleXity in health systems - MIXHS'12
Authors: Cui Tao, Matt-Mouley Bouamrane
Venue: CIKM
Year: 2012

Data management and knowledge engineering have long been important research fields in computer science, and rapid progress in recent years have increasingly seen these technologies successfully applied to solve complex biomedical challenges and support health services professionals in the course of their intellectually-demanding clinical duties, such as through the use of decision-support or expert systems. Yet, as the biomedical knowledge available in the modern digital world grows exponentially, there is a pressing need for a focused forum to promote technology and knowledge transfer from basic research to biomedical applications as well as allowing for implementers of healthcare systems to share their experiences with the research community. The Managing Interoperability and Complexity in Health Systems, MIXHS workshops are designed for such a purpose with the view that multi-disciplinary approaches within a holistic forum is essential to rise to the ever new challenges of biomedical knowledge complexity and interoperability of health systems and services.
Optimizing semantic MEDLINE for translational science studies using semantic web technologies
Authors: Cui Tao, Yuji Zhang, Guoqian Jiang, Matt-Mouley Bouamrane, Christopher G. Chute
Venue: CIKM
Year: 2012

Semantic MEDLINE provides comprehensive resources with structured annotations that have a potential to facilitate translational studies in the biomedical domain. It is computationally challenging, however, to perform queries directly from the data in the current Semantic MEDLINE database. In this research, we propose a domain pattern driven approach to optimize the Semantic MEDLINE data organization and representation for translational science studies using the Resource Description Framework (RDF) and Semantic Web technologies.
RESQ: rank-energy selective query forwarding for distributed search systems
Authors: Amin Y. Teymorian, Xiao Qin, Ophir Frieder
Venue: CIKM
Year: 2012

Selective query forwarding is a promising technique to help scale high-quality and cost-efficient query evaluation in distributed search systems. The basic idea is simple. After a local site receives a query, it determines non-local sites to forward the query to and returns an aggregation of local and non-local results. We introduce "RESQ", a hybrid rank-energy selective query forwarding model. The novel contribution of RESQ is to simultaneously consider both ranking quality and energy costs when making forwarding decisions. Using a large-scale query log and publicly-available energy price time series, we demonstrate the ability of RESQ forwarding to achieve favorable tradeoffs between the possibility of returning high ranking query results and savings in temporally- and spatially-varying energy prices.
A practical concurrent index for solid-state drives
Authors: Risi Thonangi, Shivnath Babu, Jun Yang
Venue: CIKM
Year: 2012

Solid-state drives are becoming a viable alternative to magnetic disks in database systems, but their performance characteristics, particularly those caused by their erase-before-write behavior, make conventional database indexes a poor fit. There have been various proposals of indexes specialized for these devices, but to make such indexes practical, we must address the issue of concurrency control. Good concurrency control is especially critical to indexes on solid-state drives, because they typically rely on batch updates, which may take long and block concurrent index accesses. We design, implement, and evaluate an index structure called FD+tree and an associated concurrency control scheme called FD+FC. Our evaluation confirms significant performance advantages of our approach over less sophisticated ones, and brings ou insights on data structure design and OLTP performance tuning on solid-state drives.
SliceSort: efficient sorting of hierarchical data
Authors: Quoc Trung Tran, Chee-Yong Chan
Venue: CIKM
Year: 2012

Sorting is a fundamental operation in data processing. While the problem of sorting flat data records has been extensively studied, there is very little work on sorting hierarchical data such as XML documents. Existing hierarchy-aware sorting approaches for hierarchical data are based on creating sorted subtrees as initial sorted runs and merging sorted subtrees to create the sorted output using either explicit pointers or absolute node key comparisons for merging subtrees. In this paper, we propose SliceSort, a novel, level-wise sorting technique for hierarchical data that avoids the drawbacks of subtree-based sorting techniques. Our experimental performance evaluation shows that SliceSort outperforms the state-of-art approach, HErMeS, by up to a factor of 27%.
SemaFor: semantic document indexing using semantic forests
Authors: George Tsatsaronis, Iraklis Varlamis, Kjetil Nørvåg
Venue: CIKM
Year: 2012

Traditional document indexing techniques store documents using easily accessible representations, such as inverted indices, which can efficiently scale for large document sets. These structures offer scalable and efficient solutions in text document management tasks, though, they omit the cornerstone of the documents' purpose: meaning. They also neglect semantic relations that bind terms into coherent fragments of text that convey messages. When semantic representations are employed, the documents are mapped to the space of concepts and the similarity measures are adapted appropriately to better fit the retrieval tasks. However, these methods can be slow both at indexing and retrieval time. In this paper we propose SemaFor, an indexing algorithm for text documents, which uses semantic spanning forests constructed from lexical resources, like Wikipedia, and WordNet, and spectral graph theory in order to represent documents for further processing.
Construction and maintenance of clinical pathways using data mining methods
Authors: Shusaku Tsumoto, Haruko Iwata, Shoji Hirano
Venue: CIKM
Year: 2012

This paper proposes a temporal data mining method to construct and maintain a clinical pathway used for schedule management of clinical care. The method consists of the following four steps: first, histories of nursing orders are extracted from hospital information system. Second, orders are classified into several groups by using clustering and multidimensional scaling method. Third, by using the information on groups, feature selection is applied to the data and important features for classification are extracted. Finally, original temporal data are split into several groups and the first step will be repeated. After the grouping results are stable, a new pathway is constructed based on the induced results. The method was applied to a dataset whose patients had an operation of cataracts. The results show that the reuse of stored data will give a powerful tool for maintenance of clinical pathway, which can be viewed as data-oriented management of nursing schedule.
Multi-session re-search: in pursuit of repetition and diversification
Authors: Sarah K. Tyler, Yi Zhang
Venue: CIKM
Year: 2012

Search engine users regularly re-issue queries that are the same or similar to ones they have previously issued. In this paper we study this act of query re-issuing, called re-search, focusing on multi session re-searching from an information seeking perspective. By focusing on the series of repeat or similar queries where the user shows a continued interest, new patterns of behavior not previously seen arise. We find that the well-studied re-finding behavior is only a piece of the re-search puzzle, and that even amidst repeated re-findings users exhibit diversification and novelty seeking behaviours for many re-search queries. This suggests diversity and re-finding behaviors should be jointly modelled and captured in evaluation measures, instead of being studied as two separate problems as is seen in many previous approaches.
PIKM 2012: 5th ACM workshop for PhD students in information and knowledge management
Authors: Aparna S. Varde, Fabian M. Suchanek
Venue: CIKM
Year: 2012

The PIKM 2012 workshop is the 5th of its kind after 4 successful PhD workshops at ACM CIKM. This PhD workshop invites papers that describe the Ph.D. dissertation proposals of doctoral students in any of the CIKM areas: databases, information retrieval, data mining and knowledge management. Interdisciplinary work across these tracks is particularly encouraged. This year PIKM has received around 25 submissions from over 12 countries across the globe, among which 10 have been accepted as full papers for oral presentation while 4 have been accepted as short ones for poster presentation. The selection has been conducted based on reviews submitted by an expert team comprising 21 PC members spanning 12 countries and 6 continents with a good balance of industry and academia.
Compressed data structures with relevance
Authors: Jeffrey Scott Vitter
Venue: CIKM
Year: 2012

We describe recent breakthroughs in the field of compressed data structures, in which the data structure is stored in a compressed representation that still allows fast answers to queries. We focus in particular on compressed data structures to support the important application of pattern matching on massive document collections. Given an arbitrary query pattern in textual form, the job of the data structure is to report all the locations where the pattern appears. Another variant is to report all the documents that contain at least one instance of the pattern. We are particularly interested in reporting only the most relevant documents, using a variety of notions of relevance. We discuss recently developed techniques that support fast search in these contexts as well as under additional positional and temporal constraints.
Processing continuous text queries featuring non-homogeneous scoring functions
Authors: Nelly Vouzoukidou, Bernd Amann, Vassilis Christophides
Venue: CIKM
Year: 2012

In this work we are interested in the scalable processing of content filtering queries over text item streams. In particular, we are aiming to generalize state of the art solutions with non-homogeneous scoring functions combining query-independent item importance with query-dependent content relevance. While such complex ranking functions are widely used in web search engines this is to our knowledge the first scientific work studying their usage in a continuous query scenario. Our main contribution consists in the definition and the evaluation of new efficient in-memory data structures for indexing continuous top-k queries based on an original two-dimensional representation of text queries. We are exploring locally-optimal score bounds and heuristics that efficiently prune the search space of candidate top-k query results which have to be updated at the arrival of new stream items. Finally, we experimentally evaluate memory/matching time trade-offs of these index structures. In particular we experimentally illustrate their linear scaling behavior with respect to the number of indexed queries.
BiasTrust: teaching biased users about controversial topics
Authors: V. G. Vinod Vydiswaran, ChengXiang Zhai, Dan Roth, Peter Pirolli
Venue: CIKM
Year: 2012

Deciding whether a claim is true or false often requires understanding the evidence supporting and contradicting the claim. However, when learning about a controversial claim, human biases and viewpoints may affect which evidence documents are considered "trustworthy" or credible. It is important to overcome this bias and know both viewpoints to get a balanced perspective. In this paper, we study various factors that affect learning about the truthfulness of controversial claims. We designed a user study to understand the impact of these factors. Specifically, we studied the impact of presenting evidence with contrasting viewpoints and source expertise rating on how users accessed the evidence documents. This would help us optimize how to teach users about controversial topics in the most effective way, and to design better claim verification systems. We find that users do not seek contrasting viewpoints by themselves, but explicitly presenting contrasting evidence helps them get a well-rounded understanding of the topic. Furthermore, explicit knowledge of the source credibility and the context not only affects what users read, but also how credible they perceive the document to be.