OpenRaiser/Intern-Atlas huggingface dataset:
Label constrained shortest path estimation
Authors: Ankita Likhyani, Srikanta J. Bedathur
Venue: CIKM
Year: 2013

Shortest path querying is a fundamental graph problem which is computationally quite challenging when operating over massive scale graphs. Recent results have addressed the problem of computing either exact or good approximate shortest path distances efficiently. Some of these techniques also return the path corresponding to the estimated shortest path distance fast. However, none of these techniques work very well when we have additional constraints on the labels associated with edges that constitute the path. In this paper, we develop SkIt index structure, which supports a wide range of label constraints on paths, and returns an accurate estimation of the shortest path that satisfies the constraints. We conduct experiments over graphs such as social networks, and knowledge graphs that contain millions of nodes/edges, and show that SkIt index is fast, accurate in the estimated distance and has a high recall for paths that satisfy the constraints.
Learning to handle negated language in medical records search
Authors: Nut Limsopatham, Craig Macdonald, Iadh Ounis
Venue: CIKM
Year: 2013

Negated language is frequently used by medical practitioners to indicate that a patient does not have a given medical condition. Traditionally, information retrieval systems do not distinguish between the positive and negative contexts of terms when indexing documents. For example, when searching for patients with angina, a retrieval system might wrongly consider a patient with a medical record stating ``no evidence of angina" to be relevant. While it is possible to enhance a retrieval system by taking into account the context of terms within the indexing representation of a document, some non-relevant medical records can still be ranked highly, if they include some of the query terms with the intended context. In this paper, we propose a novel learning framework that effectively handles negated language. Based on features related to the positive and negative contexts of a term, the framework learns how to appropriately weight the occurrences of the opposite context of any query term, thus preventing documents that may not be relevant from being retrieved. We thoroughly evaluate our proposed framework using the TREC 2011 and 2012 Medical Records track test collections. Our results show significant improvements over existing strong baselines. In addition, in combination with a traditional query expansion and a conceptual representation approach, our proposed framework could achieve a retrieval effectiveness comparable to the performance of the best TREC 2011 and 2012 systems, while not addressing other challenges in medical records search, such as the exploitation of semantic relationships between medical terms.
Learning to selectively rank patients' medical history
Authors: Nut Limsopatham, Craig Macdonald, Iadh Ounis
Venue: CIKM
Year: 2013

Two main approaches have emerged in the literature for the effective deployment of a search system to rank patients having a medical history relevant to a query. The first approach is to directly rank patients based on the relevance of their medical history, represented as a concatenation of their associated medical records. Instead, the second approach initially retrieves the relevant medical records of patients, and then ranks the patients based on the relevance of their retrieved medical records. However, these two approaches may be useful for different queries. In this work, we propose a novel supervised approach that can effectively identify when to use either of the two aforementioned patient ranking approaches to attain effective retrieval performance. In particular, our approach deploys a classifier to learn to select a ranking approach when ranking patients, by using query difficulty measures, such as query performance predictors and the number of medical concepts detected in a query, as learning features. We thoroughly evaluate our approach using the standard test collections provided by the TREC Medical Records track. Our results show significant improvements over existing strong baselines.
Taxonomy-based regression model for cross-domain sentiment classification
Authors: Cong-Kai Lin, Yang-Yin Lee, Chi-Hsin Yu, Hsin-Hsi Chen
Venue: CIKM
Year: 2013

Most cross-domain sentiment classification techniques consider a domain as a whole set of instances for training. However, many online shopping websites organize their data in terms of taxonomy. This paper takes Amazon shopping website as an example, and proposes a tree-structured domain representation scheme in which each node in the tree is encoded as a bit sequence to preserve its relationship with all the other nodes in the tree. To select an appropriate source node for training in the domain taxonomy, we propose a Taxonomy-Based Regression Model (TBRM) which predicts the accuracy loss from multiple source nodes to a target node using the tree-structured domain representation combined with domain similarity and domain complexity. The source node with the smallest accuracy loss is used to train a classifier which makes a prediction on the target node. The results show that our TBRM achieves better performance than the regression models without considering the taxonomy information.
MRPacker: an SQL to mapreduce optimizer
Authors: Xuelian Lin, Yue Ye, Shuai Ma
Venue: CIKM
Year: 2013

There have been recently quite a few works on optimizing the MapReduce execution plans, which either optimize the join operators or apply a set of translation rules to reduce the number of MapReduce jobs in an execution plan. However, none of these works has put into consideration and utilized how MapReduce jobs are generated and combined. To further improve the efficiency of MapReduce execution plans, we incorporate into our optimization approach the way how MapReduce jobs are generated and combined. In this paper, we propose MRPacker, a novel SQL-to-MapReduce optimizer by (a) using a set of transformation rules to reduce the number of MapReduce jobs, and (b) merging MapReduce jobs in a more reasonable way. We have finally experimentally demonstrated the effectiveness and efficiency of MRPacker, using the TPC-H benchmark.
Personalized point-of-interest recommendation by mining users' preference transition
Authors: Xin Liu, Yong Liu, Karl Aberer, Chunyan Miao
Venue: CIKM
Year: 2013

Location-based social networks (LBSNs) offer researchers rich data to study people's online activities and mobility patterns. One important application of such studies is to provide personalized point-of-interest (POI) recommendations to enhance user experience in LBSNs. Previous solutions directly predict users' preference on locations but fail to provide insights about users' preference transitions among locations. In this work, we propose a novel category-aware POI recommendation model, which exploits the transition patterns of users' preference over location categories to improve location recommendation accuracy. Our approach consists of two stages: (1) preference transition (over location categories) prediction, and (2) category-aware POI recommendation. Matrix factorization is employed to predict a user's preference transitions over categories and then her preference on locations in the corresponding categories. Real data based experiments demonstrate that our approach outperforms the state-of-the-art POI recommendation models by at least 39.75% in terms of recall.
Adaptive co-training SVM for sentiment classification on tweets
Authors: Shenghua Liu, Fuxin Li, Fangtao Li, Xueqi Cheng, Huawei Shen
Venue: CIKM
Year: 2013

Sentiment classification is an important problem in tweets mining. There lack labeled data and rating mechanism for generating them in Twitter service. And topics in Twitter are more diverse while sentiment classifiers always dedicate themselves to a specific domain or topic. Thus it is a challenge to make sentiment classification adaptive to diverse topics without sufficient labeled data. Therefore we formally propose an adaptive multiclass SVM model which transfers an initial common sentiment classifier to a topic-adaptive one. To tackle the tweet sparsity, non-text features are explored besides the conventional text features, which are intuitively split into two views. An iterative algorithm is proposed for solving this model by alternating among three steps: optimization, unlabeled data selection and adaptive feature expansion steps. The algorithm alternatively minimizes the margins of two independent objectives on different views to learn coefficient matrices, which are collaboratively used for unlabeled tweets selection from the topic that the algorithm is adapting to. And then topic-adaptive sentiment words are expended based on the above selection, in turn to help the first two steps find more confident and unlabeled tweets and boost the final performance. Comparing with the well-known supervised sentiment classifiers and semi-supervised approaches, our algorithm achieves promising increases in accuracy averagely on the 6 topics from public tweet corpus.
How do users grow up along with search engines?: a study of long-term users' behavior
Authors: Jian Liu, Yiqun Liu, Min Zhang, Shaoping Ma
Venue: CIKM
Year: 2013

With a stronger reliance on search engines in our daily life, a large number of studies have investigated user behavior characteristics in Web search. However, previous studies mainly focus on large-scale query log data and analyze temporal changes based on all users without differentiating different user groups; few have really traced a fixed and long-term group of users and have distinguished the behavior of long-term users from ordinary users to analyze long-term temporal changes unbiasedly. In this paper we look into the interaction logs of these two user groups to analyze differences between these two user groups and to better understand how users grow up along with Web search engines. Statistical and experimental results show that there exist temporal changes of both user groups. There are also significant differences between these two user groups in the frequency of interaction, complexity of search tasks, and query formulation conventions. The findings have implications for how Web search engines should better support users' information seeking process by tackling complex search tasks and complicated query formulations.
A phased ranking model for question answering
Authors: Rui Liu, Eric Nyberg
Venue: CIKM
Year: 2013

We describe a general result ranking approach for multi-phase, multi strategy information systems, which has been applied to the task of question answering (QA). Many information systems incorporate multiple steps and each step or phase may incorporate multiple component algorithms to achieve acceptable robustness and overall performance. Such systems may produce and rank a large number of candidate results. Prior work includes many models that rank a particular type of information object (e.g. a retrieved document, a factoid answer) using features specific to that information type, without attempting to make use of other non-local features (e.g. features of the upstream information source). We propose an approach that allows each phase in a system to leverage information propagated from preceding phases to inform the ranking decision. This is accomplished by a system object graph which represents all of the objects created during system execution, object dependencies (e.g. provenance), and ranking feature values extracted for a specific object. We evaluate the effectiveness of the proposed ranking approach in a multi-phase question answering system built by recombining pre-existing software modules. Experimental results show that our proposed approach significantly outperforms comparable answer ranking models.
TODMIS: mining communities from trajectories
Authors: Siyuan Liu, Shuhui Wang, Kasthuri Jayarajah, Archan Misra, Ramayya Krishnan
Venue: CIKM
Year: 2013

Existing algorithms for trajectory-based clustering usually rely on simplex representation and a single proximity-related distance (or similarity) measure. Consequently, additional information markers (e.g., social interactions or the semantics of the spatial layout) are usually ignored, leading to the inability to fully discover the communities in the trajectory database. This is especially true for human-generated trajectories, where additional fine-grained markers (e.g., movement velocity at certain locations, or the sequence of semantic spaces visited) can help capture latent relationships between cluster members. To address this limitation, we propose TODMIS: a general framework for Trajectory cOmmunity Discovery using Multiple Information Sources. TODMIS combines additional information with raw trajectory data and creates multiple similarity metrics. In our proposed approach, we first develop a novel approach for computing semantic level similarity by constructing a Markov Random Walk model from the semantically-labeled trajectory data, and then measuring similarity at the distribution level. In addition, we also extract and compute pair-wise similarity measures related to three additional markers, namely trajectory level spatial alignment (proximity), temporal patterns and multi-scale velocity statistics. Finally, after creating a single similarity metric from the weighted combination of these multiple measures, we apply dense sub-graph detection to discover the set of distinct communities. We evaluated TODMIS extensively using traces of (i) student movement data in a campus, (ii) customer trajectories in a shopping mall, and (iii) city-scale taxi movement data. Experimental results demonstrate that TODMIS correctly and efficiently discovers the real grouping behaviors in these diverse settings.
Efficiently anonymizing social networks with reachability preservation
Authors: Xiangyu Liu, Bin Wang, Xiaochun Yang
Venue: CIKM
Year: 2013

The goal of graph anonymization is avoiding disclosure of privacy in social networks through graph modifications meanwhile preserving data utility of the anonymized graph for social network analysis. Graph reachability is an important data utility as reachability queries are not only common on graph databases, but also serving as fundamental operations for many other graph queries. However, the graph reachability is severely distorted after the anonymization. In this paper, we solve this problem by designing a reachability preserving anonymization (RPA for short) algorithm. The main idea of RPA is to organize vertices into groups and greedily anonymizes each vertex with low anonymization cost on reachability. We propose the reachable interval to efficiently measure the anonymization cost incurred by an edge addition, which guarantees the high efficiency of RPA. Extensive experiments illustrate that anonymized social networks generated by our methods preserve high utility on reachability.
Structured positional entity language model for enterprise entity retrieval
Authors: Chunliang Lu, Lidong Bing, Wai Lam
Venue: CIKM
Year: 2013

We investigate the problem of general entity retrieval for enterprise websites. Our framework transforms the webpage content into a structured content representation, which captures hierarchical information blocks and semi-structured data records information. To facilitate entity retrieval given a user query, we develop a structured positional entity language model suitable for ranking entities extracted from the webpage content incorporating the structured content representation. Different from existing language models for retrieval, our proposed model considers both the proximity and the structured webpage content in a unified manner. Extensive experiments on the benchmark datasets demonstrate the effectiveness of our proposed framework.
TerraFly GeoCloud: online spatial data analysis system
Authors: Yun Lu, Mingjin Zhang, Tao Li, Chang Liu, Erik Edrosa, Naphtali Rishe
Venue: CIKM
Year: 2013

With the exponential growth of the usage of web map services, the geo data analysis has become more and more popular. This paper develops an online Spatial Data Analysis System, TerraFly GeoCloud, which facilitates the end user to visualize and analyze spatial data, and to share the analysis results. Built on the TerraFly Geo spatial database, TerraFly GeoCloud is an extra layer running upon TerraFly map supporting many different visualization functions and spatial data analysis models. TerraFly GeoCloud also enables the MapQL technology to create maps using SQL-like statements. The TerraFly GeoCloud system is available at http://terrafly.fiu.edu/GeoCloud/.
External memory K-bisimulation reduction of big graphs
Authors: Yongming Luo, George H. L. Fletcher, Jan Hidders, Yuqing Wu, Paul De Bra
Venue: CIKM
Year: 2013

In this paper, we present, to our knowledge, the first known I/O efficient solutions for computing the k-bisimulation partition of a massive directed graph, and performing maintenance of such a partition upon updates to the underlying graph. Ubiquitous in the theory and application of graph data, bisimulation is a robust notion of node equivalence which intuitively groups together nodes in a graph which share fundamental structural features. k-bisimulation is the standard variant of bisimulation where the topological features of nodes are only considered within a local neighborhood of radius k > 0.
Hotness-aware buffer management for flash-based hybrid storage systems
Authors: Yanfei Lv, Bin Cui, Xuexuan Chen, Jing Li
Venue: CIKM
Year: 2013

Flash solid-state drives (SSDs) provide much faster access to data compared with traditional hard disk drives (HDDs). The current price and performance of SSD suggest it can be adopted as a data buffer between main memory and HDD, and buffer management policy in such hybrid systems has attracted more and more interest from research community recently. In this paper, we propose a novel approach to manage the buffer in flash-based hybrid storage systems, named Hotness Aware Hit (HAT). HAT exploits a page reference queue to record the access history as well as the status of accessed pages, i.e., hot, warm and cold. Additionally, the page reference queue is further split into hot and warm regions which correspond to the memory and flash in general. The HAT approach updates the page status and deals with the page migration in the memory hierarchy according to the current page status and hit position in the page reference queue. Our empirical evaluation on benchmark traces demonstrates the superiority of the proposed strategy against the state-of-the-art competitors.
Local clustering in provenance graphs
Authors: Peter Macko, Daniel W. Margo, Margo I. Seltzer
Venue: CIKM
Year: 2013

Systems that capture and store data provenance, the record of how an object has arrived at its current state, accumulate historical metadata over time, forming a large graph. Local clustering in these graphs, in which we start with a seed vertex and grow a cluster around it, is of paramount importance because it supports critical provenance applications such as identifying semantically meaningful tasks in an object's history. However, generic graph clustering algorithms are not effective at these tasks. We identify three key properties of provenance graphs and exploit them to justify two new centrality metrics we developed for use in performing local clustering on provenance graphs.
SkyView: a user evaluation of the skyline operator
Authors: Matteo Magnani, Ira Assent, Kasper Hornbæk, Mikkel R. Jakobsen, Ken Friis Larsen
Venue: CIKM
Year: 2013

The skyline operator has recently emerged as an alternative to ranking queries. It retrieves a number of potential best options for arbitrary monotone preference functions. The success of this operator in the database community is based on the belief that users benefit from the limited effort required to specify skyline queries compared to, for instance, ranking. While application examples of the skyline operator exist, there is no principled analysis of its benefits and limitations in data retrieval tasks. Our study investigates the degree to which users understand skyline queries, how they specify query parameters and how they interact with skyline results made available in listings or map-based interfaces.
ImG-complex: graph data model for topology of unstructured meshes
Authors: Alireza Rezaei Mahdiraji, Peter Baumann, Guntram Berti
Venue: CIKM
Year: 2013

Although, many applications use unstructured meshes, there is no specialized mesh database which supports storing and querying mesh data. Existing mesh libraries do not support declarative querying and are expensive to maintain. A mesh database can benefit the domains in several ways such as: declarative query language, ease of maintenance, etc. In this paper, we propose the Incidence multi-Graph Complex (ImG-Complex) data model for storing topological aspects of meshes in a database. ImG-Complex extends incidence graph (IG) model with multi-incidence information to represent a new object class which we call ImG-Complexes. We introduce optional and application-specific constraints to limit the ImG model to smaller object classes and validate mesh structures based on the modeled object class properties. We show how Neo4j graph database can be used to query mesh topology based on the (possibly constrained) ImG model. Finally, we experiment Neo4j and PostgreSQL performance on executing topological mesh queries.
DUBMOD13: international workshop on data-driven user behavioral modelling and mining from social media
Authors: Jalal Mahmud, Jeffrey Nichols, Michelle X. Zhou, James Caverlee, John O&apos, Donovan
Venue: CIKM
Year: 2013

Massive amounts of data are being generated on social media sites, such as Twitter and Facebook. These data can be used to better understand people (e.g., personality traits, perceptions, and preferences) and predict their behavior. As a result, a deeper understanding of users and their behavior can benefit a wide range of intelligent applications, such as advertising, social recommender systems, and personalized knowledge management. These applications will also benefit individual users themselves and optimize their experience across a wide variety of domains, such as retail, healthcare, and education. Since mining and understanding user behavior from social media often requires interdisciplinary effort, including machine learning, text mining, human-computer interaction, and social science, our workshop aims to bring together researchers and practitioners from multiple fields to discuss the creation of deeper models of individual users by mining the content that they publish and the social networking behavior that they exhibit.
Network-aware search in social tagging applications: instance optimality versus efficiency
Authors: Silviu Maniu, Bogdan Cautis
Venue: CIKM
Year: 2013

We consider in this paper top-k query answering in social applications, with a focus on social tagging. This problem requires a significant departure from socially agnostic techniques. In a network- aware context, one can (and should) exploit the social links, which can indicate how users relate to the seeker and how much weight their tagging actions should have in the result build-up. We propose algorithms that have the potential to scale to current applications. While the problem has already been considered in previous literature, this was done either under strong simplifying assumptions or under choices that cannot scale to even moderate-size real-world applications. We first revisit a key aspect of the problem, which is accessing the closest or most relevant users for a given seeker. We describe how this can be done on the fly (without any pre- computations) for several possible choices -- arguably the most natural ones -- of proximity computation in a user network. Based on this, our top-k algorithm is sound and complete, addressing the applicability issues of the existing ones. Moreover, it performs significantly better in general and is instance optimal in the case when the search relies exclusively on the social weight of tagging actions.