OpenRaiser/Intern-Atlas huggingface dataset:
Large-scale Robust Online Matching and Its Application in E-commerce
Authors: Rong Jin
Venue: CIKM
Year: 2016

This talk will be focused on large-scale matching problem that aims to find the optimal assignment of tasks to different agents under linear constraints. Large-scale matching has found numerous applications in e-commerce. An well known example is budget aware online advertisement. A common practice in online advertisement is to find, for each opportunity or user, the advertisements that fit best with his/her interests. The main shortcoming with this greedy approach is that it did not take into account the budget limits set by advertisers. Our studies, as well as others, have shown that by carefully taking into budget limits of individual advertisers, we could significantly improve the performance of the advertisement system. Despite of rich literature, two important issues are often overlooked in the previous studies of matching/assignment problem. The first issues arises from the fact that most quantities used by optimization are estimated based on historical data and therefore are likely to be inaccurate and unreliable. The second challenge is how to perform online matching as in many e-commerce problems, tasks are created in an online fashion and algorithm has to make assignment decision immediately when every task emerges. We refer to these two issues as challenges of "robust matching" and "online matching".
Hybrid Indexing for Versioned Document Search with Cluster-based Retrieval
Authors: Xin Jin, Daniel Agun, Tao Yang, Qinghao Wu, Yifan Shen, Susen Zhao
Venue: CIKM
Year: 2016

The previous two-phase method for searching versioned documents seeks a cost tradeoff by using non-positional information to rank document versions first. The second phase then re-ranks top document versions using positional information with fragment-based index compression. This paper proposes an alternative approach that uses cluster-based retrieval to quickly narrow the search scope guided by version representatives at Phase 1 and develops a hybrid index structure with adaptive runtime data traversal to speed up Phase 2 search. The hybrid scheme exploits the advantages of forward index and inverted index based on the term characteristics to minimize the time in extracting positional and other feature information during runtime search. This paper compares several indexing and data traversal options with different time and space tradeoffs and describes evaluation results to demonstrate their effectiveness. The experiment results show that the proposed scheme can be up-to about 4x as fast as the previous work on solid state drives while retaining good relevance.
Data Locality in Graph Engines: Implications and Preliminary Experimental Results
Authors: Yong-Yeon Jo, Jiwon Hong, Myung-Hwan Jang, Jae-Geun Bang, Sang-Wook Kim
Venue: CIKM
Year: 2016

The size of graphs has dramatically increased. Graph engines for a single machine have been emerged to process these graphs efficiently. However, existing engines have overlooked a data locality which is an imperative factor to improve the performance of these engines in the previous literature. In this paper, we show the importance of data locality with graph algorithms by running on graph engines based on a single machine.
A Filtering-based Clustering Algorithm for Improving Spatio-temporal Kriging Interpolation Accuracy
Authors: Qiao Kang, Wei-keng Liao, Ankit Agrawal, Alok N. Choudhary
Venue: CIKM
Year: 2016

Geostatistical interpolation is the process that uses existing data and statistical models as inputs to predict data in unobserved spatio-temporal contexts as output. Kriging is a well-known geostatistical interpolation method that minimizes mean square error of prediction. The result interpolated by Kriging is accurate when consistency of statistical properties in data is assumed. However, without this assumption, Kriging interpolation has poor accuracy. To address this problem, this paper presents a new filtering-based clustering algorithm that partitions data into clusters such that the interpolation error within each cluster is significantly reduced, which in turn improves the overall accuracy. Comparisons to traditional Kriging are made with two real-world datasets using two error criteria: normalized mean square error(NMSE) and χ2 test statistics for normalized deviation measurement. Our method has reduced NMSE by more than 50% for both datasets over traditional Kriging. Moreover, χ2 tests have also shown significant improvements of our approach over traditional Kriging.
eGraphSearch: Effective Keyword Search in Graphs
Authors: Mehdi Kargar, Lukasz Golab, Jaroslaw Szlichta
Venue: CIKM
Year: 2016

In a node-labeled graph, keyword search finds subtrees of the graph whose nodes contain all of the query keywords. This provides a way to query graph databases that neither requires mastery of a query language such as SPARQL, nor a deep knowledge of the database schema. We demonstrate eGraphSearch, a new system for effective keyword search in graph databases. Previous work ranks answer trees using combinations of structural and content-based metrics, such as path length between keywords or relevance of the labels in the answer tree to the query keywords. However, different nodes in the graph might have different importance, which affects the utility of the answer. In the proposed system, we implemented two new ways to rank keyword search results over graphs: the first one takes node importance into account while the second one is a bi-objective optimization of edge weights and node importance. In the demonstration, participants will execute keyword queries against several popular graph datasets.
LICON: A Linear Weighting Scheme for the Contribution ofInput Variables in Deep Artificial Neural Networks
Authors: Gjergji Kasneci, Thomas Gottron
Venue: CIKM
Year: 2016

In recent years artificial neural networks have become the method of choice for many pattern recognition tasks. Despite their overwhelming success, a rigorous and easy to interpret mathematical explanation of the influence of input variables on a output produced by a neural network is still missing.
Learning to Account for Good Abandonment in Search Success Metrics
Authors: Madian Khabsa, Aidan C. Crook, Ahmed Hassan Awadallah, Imed Zitouni, Tasos Anastasakos, Kyle Williams
Venue: CIKM
Year: 2016

Abandonment in web search has been widely used as a proxy to measure user satisfaction. Initially it was considered a signal of dissatisfaction, however with search engines moving towards providing answer-like results, a new category of abandonment was introduced and referred to as Good Abandonment. Predicting good abandonment is a hard problem and it was the subject of several previous studies. All those studies have focused, though, on predicting good abandonment in offline settings using manually labeled data. Thus, it remained a challenge how to have an online metric that accounts for good abandonment. In this work we describe how a search success metric can be augmented to account for good abandonment sessions using a machine learned metric that depends on user's viewport information. We use real user traffic from millions of users to evaluate the proposed metric in an A/B experiment. We show that taking good abandonment into consideration has a significant effect on the overall performance of the online metric.
Towards Time-Discounted Influence Maximization
Authors: Arijit Khan
Venue: CIKM
Year: 2016

The classical influence maximization (IM) problem in social networks does not distinguish between whether a campaign gets viral in a week or in a year. From the practical standpoint, however, campaigns for a new technology or an upcoming movie must be spread as quickly as possible, otherwise they will be obsolete. To this end, we formulate and investigate the novel problem of maximizing the time-discounted influence spread in a social network, that is, the campaigner is interested in both "when" and "how likely" a user would be influenced. In particular, we assume that the campaigner has a utility function which monotonically decreases with the time required for a user to get influenced, since the activation of the seed nodes. The problem that we solve in this paper is to maximize the expected aggregated value of this utility function over all network users. This is a novel and relevant problem that, surprisingly, has not been studied before. Time-discounted influence maximization (TDIM), being a generalization of the classical IM, still remains NP-hard. However, our main contribution is to prove the sub-modularity of the objective function for any monotonically decreasing function of time, under a variety of influence cascading models, e.g., the independent cascade, linear threshold, and maximum influence arborescence models, thereby designing approximate algorithms with theoretical performance guarantees. We also illustrate that the existing optimization techniques (e.g., CELF) for influence maximization are more efficient over TDIM. Our experimental results demonstrate the effectiveness of our solutions over several baselines including the classical influence maximization algorithms.
Attribute-based Crowd Entity Resolution
Authors: Asif R. Khan, Hector Garcia-Molina
Venue: CIKM
Year: 2016

We study the problem of using the crowd to perform entity resolution (ER) on a set of records. For many types of records, especially those involving images, such a task can be difficult for machines, but relatively easy for humans. Typical crowd-based ER approaches ask workers for pairwise judgments between records, which quickly becomes prohibitively expensive even for moderate numbers of records. In this paper, we reduce the cost of pairwise crowd ER approaches by soliciting the crowd for attribute labels on records, and then asking for pairwise judgments only between records with similar sets of attribute labels. However, due to errors induced by crowd-based attribute labeling, a naive attribute-based approach becomes extremely inaccurate even with few attributes. To combat these errors, we use error mitigation strategies which allow us to control the accuracy of our results while maintaining significant cost reductions. We develop a probabilistic model which allows us to determine the optimal, lowest-cost combination of error mitigation strategies needed to achieve a minimum desired accuracy. We test our approach with actual crowdworkers on a dataset of celebrity images, and find that our results yield crowd ER strategies which achieve high accuracy yet are significantly lower cost than pairwise-only approaches.
DTMBIO 2016: The Tenth International Workshop on Data and Text Mining in Biomedical Informatics
Authors: Sangwoo Kim, Jake Y. Chen, Vincenzo Cutello, Doheon Lee
Venue: CIKM
Year: 2016

Started in 2006 as a specialized workshop in the field of text mining applied to biomedical informatics, DTMBIO (ACM international workshop on Data and Text Mining in Biomedical Informatics) has been held annually in conjunction with one of the largest data management conferences, CIKM, bringing together researchers working on computer science and bioinformatics area. The purpose of DTMBIO is to foster discussions regarding the state-of-the-art applications of data and text mining on biomedical research problems. DTMBIO 2016 will help scientists navigate emerging trends and opportunities in the evolving area of informatics related techniques and problems in the context of biomedical research.
Pagination versus Scrolling in Mobile Web Search
Authors: Jaewon Kim, Paul Thomas, Ramesh S. Sankaranarayana, Tom Gedeon, Hwan-Jin Yoon
Venue: CIKM
Year: 2016

Vertical scrolling is the standard method of exploring search results pages. For touch-enabled mobile devices that are not equipped with a mouse or keyboard, we adopt other methods of controlling the viewport with the aim of investigating user interaction. From the intuition that people are used to reading books by turning pages horizontally, we conducted a user experiment to investigate the effects of horizontal and vertical control types (pagination versus scrolling) on a touch-enabled mobile phone. Our findings suggest that participants using pagination were more likely to find relevant documents, especially those over the fold; spent more time attending to relevant results; and were faster to click while spending less time on the search result pages overall. We also found that the main reason for the difference in search speed is the time taken for the scroll itself. We conclude that search engines need to provide different viewport controls to allow better search experiences on touch-enabled mobile devices.
Qualitative Cleaning of Uncertain Data
Authors: Henning Köhler, Sebastian Link
Venue: CIKM
Year: 2016

We propose a new view on data cleaning: Not data itself but the degrees of uncertainty attributed to data are dirty. Applying possibility theory, tuples are assigned degrees of possibility with which they occur, and constraints are assigned degrees of certainty that say to which tuples they apply. Classical data cleaning modifies some minimal set of tuples. Instead, we marginally reduce their degrees of possibility. This reduction leads to a new qualitative version of the vertex cover problem. Qualitative vertex cover can be mapped to a linear-weighted constraint satisfaction problem. However, any off-the-shelf solver cannot solve the problem more efficiently than classical vertex cover. Instead, we utilize the degrees of possibility and certainty to develop a dedicated algorithm that is fixed parameter tractable in the size of the qualitative vertex cover. Experiments show that our algorithm is faster than solvers for the classical vertex cover problem by several orders of magnitude, and performance improves with higher numbers of uncertainty degrees.
Precision-Oriented Query Facet Extraction
Authors: Weize Kong, James Allan
Venue: CIKM
Year: 2016

Faceted search has been used successfully for many vertical applications such as e-commerce and digital libraries. However, it remains challenging to extend faceted search to the open-domain web due to the large and heterogeneous nature of the web. Recent work proposed an alternative solution that extracts facets for queries from their web search results, but neglected the precision-oriented perspective of the task -- users are likely to care more about precision of presented facets than recall.
Query Expansion Using Word Embeddings
Authors: Saar Kuzi, Anna Shtok, Oren Kurland
Venue: CIKM
Year: 2016

We present a suite of query expansion methods that are based on word embeddings. Using Word2Vec's CBOW embedding approach, applied over the entire corpus on which search is performed, we select terms that are semantically related to the query. Our methods either use the terms to expand the original query or integrate them with the effective pseudo-feedback-based relevance model. In the former case, retrieval performance is significantly better than that of using only the query, and in the latter case the performance is significantly better than that of the relevance model.
An Experimental Comparison of Iterative MapReduce Frameworks
Authors: Haejoon Lee, Minseo Kang, Sun-Bum Youn, Jae-Gil Lee, YongChul Kwon
Venue: CIKM
Year: 2016

MapReduce has become a dominant framework in big data analysis, and thus there have been significant efforts to implement various data analysis algorithms in MapReduce. Many data analysis algorithms are inherently iterative, repeating the same set of tasks until a convergence. To efficiently support iterative algorithms at scale, a few variants of Hadoop and new platforms have been proposed and actively developed in both academia and industry. Representative systems include HaLoop, iMapReduce, Twister, and Spark. In this paper, we experimentally compare Hadoop and the aforementioned systems using various workloads and metrics. The five systems are compared through four iterative algorithms---PageRank, recursive query, k-means, and logistic regression---on 50 Amazon EC2 machines (200 cores in total). We thoroughly explore the effectiveness of their new caching, communication, and scheduling mechanisms in support of iterative computation. Our evaluation also shows the performance depending on data skewness and memory residency. Overall, we believe that our evaluation and interpretation will be useful for designing a new framework or improving the existing ones.
Quark-X: An Efficient Top-K Processing Framework for RDF Quad Stores
Authors: Jyoti Leeka, Srikanta Bedathur, Debajyoti Bera, Medha Atre
Venue: CIKM
Year: 2016

There is a growing trend towards enriching the RDF content from its classical Subject-Predicate-Object triple form to an annotated representation which can model richer relationships such as including fact provenance, fact confidence, higher-order relationships and so on. One of the recommended ways to achieve this is to use reification and represent it as N-Quads "or simply quads" where an additional identifier is associated with the entire RDF statement which can then be used to add further annotations. A typical use of such annotations is to have quantifiable confidence values to be attached to facts. In such settings, it is important to support efficient top-k queries, typically over user-defined ranking functions containing sentence level confidence values in addition to other quantifiable values in the database. In this paper, we present Quark-X, an RDF-store and SPARQL processing system for reified RDF data represented in the form of quads. This paper presents the overall architecture of our system -- illustrating the modifications which need to be made to a native quad store for it to process top-k queries. In Quark-X, we propose indexing and query processing techniques for making top-k querying efficient. In addition, we present the results of a comprehensive empirical evaluation of our system over Yago2S and DBpedia datasets. Our performance study shows that the proposed method achieves one to two order of magnitude speed-up over baseline solutions.
Selective Cluster-Based Document Retrieval
Authors: Or Levi, Fiana Raiber, Oren Kurland, Ido Guy
Venue: CIKM
Year: 2016

We address the long standing challenge of selective cluster-based retrieval; namely, deciding on a per-query basis whether to apply cluster-based document retrieval or standard document retrieval. To address this classification task, we propose a few sets of features based on those utilized by the cluster-based ranker, query-performance predictors, and properties of the clustering structure. Empirical evaluation shows that our method outperforms state-of-the-art retrieval approaches, including cluster-based, query expansion, and term proximity methods.
Efficient Processing of Location-Aware Group Preference Queries
Authors: Miao Li, Lisi Chen, Gao Cong, Yu Gu, Ge Yu
Venue: CIKM
Year: 2016

With the proliferation of geo-positioning techniques that enable users to acquire their geographical positions, there has been increasing popularity of online location-based services. This development has generated a large volume of points of interest labeled with category features (e.g., hotel, resort, stores, stations, and tourist attractions). It gives prominence to various types of spatial-keyword queries, which are employed to provide fundamental querying functionality for location-based services.
Approximating Graph Pattern Queries Using Views
Authors: Jia Li, Yang Cao, Xudong Liu
Venue: CIKM
Year: 2016

This paper studies approximation of graph pattern queries using views. Given a pattern query Q and a set V of views, we propose to find a pair of queries Qu and Ql, referred to as the upper and lower approximations of Q w.r.t. V, such that (a) for any data graph G, answers to (part of) Q in G are contained in Qu(G) and contain Ql(G); and (b) both Qu and Ql can be answered by using views in V. We consider pattern queries based on both graph simulation and subgraph isomorphism. We study fundamental problems about approximation using views. Given Q and V, (1) we study whether there exist upper and lower approximations of Q w.r.t. V. (2) How to find approximations that are closest to Q w.r.t. V if exist? (3) How to answer upper and lower approximations using views in V? We give characterizations of the problems, study their complexity and approximation-hardness, and develop algorithms with provable bounds. Using real-life datasets, we verify the effectiveness and efficiency of approximating simulation and subgraph queries using views.
Automatic Generation and Validation of Road Maps from GPS Trajectory Data Sets
Authors: Hengfeng Li, Lars Kulik, Kotagiri Ramamohanarao
Venue: CIKM
Year: 2016

With the popularity of mobile GPS devices such as on-board navigation systems and smart phones, users can contribute their GPS trajectory data for creating geo-volunteered road maps. However, the quality of these road maps cannot be guaranteed due to the lack of expertise among contributing users. Therefore, important challenges are (i) to automatically generate accurate roads from GPS traces and (ii) to validate the correctness of existing road maps. To address these challenges, we propose a novel Spatial-Linear Clustering (SLC) technique to infer road segments from GPS traces. In our algorithm, we propose the use of spatial-linear clusters to appropriately represent the linear nature of GPS points collected from the same road segment. Through inferring road segments our algorithm can detect missing roads and checking the correctness of existing road network. For our evaluation, we conduct extensive experiments that compare our method to the state-of-the-art methods on two real data sets. The experimental results show that the F1 score of our algorithm is on average 10.7% higher than the best state-of-the-art method.
On Transductive Classification in Heterogeneous Information Networks
Authors: Xiang Li, Ben Kao, Yudian Zheng, Zhipeng Huang
Venue: CIKM
Year: 2016

A heterogeneous information network (HIN) is used to model objects of different types and their relationships. Objects are often associated with properties such as labels. In many applications, such as curated knowledge bases for which object labels are manually given, only a small fraction of the objects are labeled. Studies have shown that transductive classification is an effective way to classify and to deduce labels of objects, and a number of transductive classifiers have been put forward to classify objects in an HIN. We study the performance of a few representative transductive classification algorithms on HINs. We identify two fundamental properties, namely, cohesiveness and connectedness, of an HIN that greatly influence the effectiveness of transductive classifiers. We define metrics that measure the two properties. Through experiments, we show that the two properties serve as very effective indicators that predict the accuracy of transductive classifiers. Based on cohesiveness and connectedness we derive (1) a black-box tester that evaluates whether transductive classifiers should be applied for a given classification task and (2) an active learning algorithm that identifies the objects in an HIN whose labels should be sought in order to improve classification accuracy.