OpenRaiser/Intern-Atlas huggingface dataset:
MAGIK: managing completeness of data
Authors: Ognjen Savkovic, Paramita Mirza, Sergey Paramonov, Werner Nutt
Venue: CIKM
Year: 2012

MAGIK demonstrates how to use meta-information about the completeness of a database to assess the quality of the answers returned by a query. The system holds so-called table-completeness (TC) statements, by which one can express that a table is partially complete, that is, it contains all facts about some aspect of the domain. Given a query, MAGIK determines from such meta-information whether the database contains sufficient data for the query answer to be complete. If, according to the TC statements, the database content is not sufficient for a complete answer, MAGIK explains which further TC statements are needed to guarantee completeness. MAGIK extends and complements theoretical work on modeling and reasoning about data completeness by providing the first implementation of a reasoner. The reasoner operates by translating completeness reasoning tasks into logic programs, which are executed by an answer set engine.
Moving from descriptive to causal analytics: case study of discovering knowledge from us health indicators warehouse
Authors: Jack C. Schryver, Mallikarjun Shankar, Songhua Xu
Venue: CIKM
Year: 2012

The knowledge management community has introduced a multitude of methods for knowledge discovery on large datasets. In the context of public health intelligence, we integrated and incorporated some of these methods into an analyst's workflow that proceeds from the data-centric descriptive level of analysis to the model-centric causal level of reasoning. We show several case studies of the proposed analyst's workflow as applied to the US Health Indicators Warehouse (HIW), which is a medium scale, public dataset regarding community health information as collected by the US federal government. In our case studies, we demonstrate a series of visual analytics efforts targeted at the HIW, including visual analysis according to correlation matrices, multivariate outlier analysis, multiple linear regression of Medicare costs, confirmatory factor analysis, and hybrid scatterplot and heatmap visualization for distributions of a group of health indicators. We conclude by sketching a preliminary framework for examining causal dependence hypotheses for future data science research in public health.
Multilevel business process modeling: motivation, approach, design issues, and applications
Authors: Christoph G. Schütz, Michael Schrefl, Lois M. L. Delcambre
Venue: CIKM
Year: 2012

Conceptual models organize the data as well as the processes from a business domain using a human-readable, yet formal representation language. For static data models, various modeling approaches have been proposed to represent complex multilevel abstraction hierarchies. For process models, though, current modeling approaches do not provide a flexible and powerful formalism for representing complex multilevel abstraction hierarchies. In this paper, we motivate the need for multilevel business process models, present our initial approach, and sketch future research in this area.
Semantic annotation: what about quality?
Authors: Sana Sellami, Claudia C. Gutiérrez Rodriguez
Venue: CIKM
Year: 2012

This paper outlines an ongoing research focused on the quality analysis of semantic annotation towards better Web Services management. Considering the properties of the annotation process and result, we provide an overview of the main issues related to the semantic annotation of Web Services and our first clues to tackle this relevant issue.
Learning spectral embedding via iterative eigenvalue thresholding
Authors: Fanhua Shang, Licheng Jiao, Yuanyuan Liu, Fei Wang
Venue: CIKM
Year: 2012

Learning data representation is a fundamental problem in data mining and machine learning. Spectral embedding is one popular method for learning effective data representations. In this paper we propose a novel framework to learn enhanced spectral embedding, which not only considers the geometrical structure of the data space, but also takes advantage of the given pairwise constraints. The proposed formulation can be solved by an iterative eigenvalue thresholding (IET) algorithm. Specially, we convert the problem of learning spectral embedding with pairwise constraints into the one of completing an "ideal" kernel matrix. And we introduce the spectral embedding of graph Laplacian as the auxiliary information and cast it as a small-scale positive semidefinite (PSD) matrix optimization problem with nuclear norm regularization. Then, we develop an IET algorithm to solve it efficiently. Moreover, we also present an effective semi-supervised clustering (SSC) approach with learned spectral embedding (LSE). Finally, we validate the proposed IET algorithm and LSE approach by extensive experiments on real-world data sets.
Loyalty-based selection: retrieving objects that persistently satisfy criteria
Authors: Zhitao Shen, Muhammad Aamir Cheema, Xuemin Lin
Venue: CIKM
Year: 2012

A traditional query returns a set of objects that satisfy user defined criteria at the time query was issued. The results are based on the values of objects at query time and may be affected by outliers. Intuitively, an object better meets the user's needs if it persistently satisfies the criteria, i.e., it satisfies the criteria for majority of the time in the past T time units. In this paper, we propose a measure named loyalty that reflects how persistently an object satisfies the criteria. Formally, the loyalty of an object is the total time (in past T time units) it satisfies the query criteria. In this paper, we study top-k loyalty queries over sliding windows that continuously report k objects with the highest loyalties. Each object issues an update when it starts satisfying the criteria or when it stops satisfying the criteria. We show that the lower bound cost of updating the results of a top-k loyalty query is O(logN), for each object update, where N is the number of updates issued in last T time units. We conduct a detailed complexity analysis and show that our proposed algorithm is optimal. Moreover, effective pruning techniques are proposed to improve the efficiency. We experimentally verify the effectiveness of the proposed approach by comparing it with a classic sweep line algorithm.
Large-scale item categorization for e-commerce
Authors: Dan Shen, Jean-David Ruvini, Badrul Sarwar
Venue: CIKM
Year: 2012

This paper studies the problem of leveraging computationally intensive classification algorithms for large scale text categorization problems. We propose a hierarchical approach which decomposes the classification problem into a coarse level task and a fine level task. A simple yet scalable classifier is applied to perform the coarse level classification while a more sophisticated model is used to separate classes at the fine level. However, instead of relying on a human-defined hierarchy to decompose the problem, we we use a graph algorithm to discover automatically groups of highly similar classes. As an illustrative example, we apply our approach to real-world industrial data from eBay, a major e-commerce site where the goal is to classify live items into a large taxonomy of categories. In such industrial setting, classification is very challenging due to the number of classes, the amount of training data, the size of the feature space and the real-world requirements on the response time. We demonstrate through extensive experimental evaluation that (1) the proposed hierarchical approach is superior to flat models, and (2) the data-driven extraction of latent groups works significantly better than the existing human-defined hierarchy.
You can stop early with COLA: online processing of aggregate queries in the cloud
Authors: Yingjie Shi, Xiaofeng Meng, Fusheng Wang, Yantao Gan
Venue: CIKM
Year: 2012

Cloud-based data management systems are emerging as scalable, fault-tolerant, and efficient solutions to manage large volumes of data with cost effective infrastructures, and more and more data analysis applications are migrated to the cloud. As an attractive solution to provide a quick sketch of massive data before a long wait of the final accurate query result, online processing of aggregate queries in the cloud is of paramount importance. This problem is challenging to solve because of the large block based data organization and distributed processing mode in the cloud. In this paper, we present COLA, a system for Cloud Online Aggregation to provide progressive approximate answers for both single tables and joined multiple tables. We develop an online query processing algorithm for MapReduce to support incremental and continuous computing of aggregations on joins which minimizes the waiting time before an acceptable estimate is achieved. We formulate a statistical foundation that supports block-level sampling for single-table online aggregations and effective estimation of approximate results and confidence intervals of statistical significance. We also develop a two-phase stratified sampling method to support multi-table aggregations to improve the approximate query answers and speed up the convergence of confidence intervals. We implement COLA in Hadoop, and our experiments demonstrate that COLA can deliver reasonable precise online estimates within a time period two orders of magnitude shorter than that used to produce exact answers.
Simultaneous realization of page-centric communication and search
Authors: Yuhki Shiraishi, Jianwei Zhang, Yukiko Kawai, Toyokazu Akiyama
Venue: CIKM
Year: 2012

We present a novel system that combines the advantages of social communication and Web search by simultaneously discovering important pages and users. First, the system provides a communication interface attached to pages, which allows users to talk with each other in real time while browsing the same page, i.e., page-centric communication. Then, the system can efficiently provide two ranking lists of pages and users by analyzing a hybrid structure of hyperlinks (page-page relationship) and social links (page-user relationship and user-user relationship). Thus, users can efficiently search for important pages as well as important users related to their queries through the ranking function, and immediately obtain useful information or knowledge from not only pages themselves but also from other users.
Influence propagation in adversarial setting: how to defeat competition with least amount of investment
Authors: Shahrzad Shirazipourazad, Brian Bogard, Harsh Vachhani, Arunabha Sen, Paul Horn
Venue: CIKM
Year: 2012

It has been observed that individuals' decisions to adopt a product or innovation are often influenced by the recommendations of their friends and acquaintances. Motivated by this observation, the last few years have seen a number of studies on influence maximization in social networks. The primary goal of these studies is identification of k most influential nodes in a network. A major limitation of these studies is that they focus on a non-adversarial environment, where only one player is engaged in influencing the nodes. However, in a realistic scenario multiple players attempt to influence the nodes in a competitive fashion. The proposed model considers a competitive environment where a node that has not yet adopted an innovation, can adopt only one of the several competing innovations and once it adopts an innovation, it does not switch. The paper studies the scenario where the first player has already chosen a set of k nodes and the second player, with the knowledge of the choice of the first, attempts to identify a smallest set of nodes (excluding the ones already chosen by the first) so that when the influence propagation process ends, the number of nodes influenced by the second player is larger than the number of nodes influenced by the first.
Stochastic simulation of time-biased gain
Authors: Mark D. Smucker, Charles L. A. Clarke
Venue: CIKM
Year: 2012

Time-biased gain provides a unifying framework for information retrieval evaluation, generalizing many traditional effectiveness measures while accommodating aspects of user behavior not captured by these measures. By using time as a basis for calibration against actual user data, time-biased gain can reflect aspects of the search process that directly impact user experience, including document length, near-duplicate documents, and summaries. Unlike traditional measures, which must be arbitrarily normalized for averaging purposes, time-biased gain is reported in meaningful units, such as the total number of relevant documents seen by the user. In prior work, we proposed and validated a closed-form equation for estimating time-biased gain, explored its properties, and compared it to standard approaches. In this paper, we use stochastic simulation to numerically approximate time-biased gain. Stochastic simulation provides greater flexibility that will allow us, in future work, to easily accommodate different types of user behavior and increase the realism of the effectiveness measure.
Exploiting semantic annotations in math information retrieval
Authors: Petr Sojka
Venue: CIKM
Year: 2012

This paper describes exploitation of semantic annotations in the design and architecture of MIaS (Math Indexer and Searcher) system for mathematics retrieval. Basing on the claim that navigational and research search are `killer' applications for digital library such as the European Digital Mathematics Library, EuDML, we argue for an approach based on Natural Language Processing techniques as used in corpus management systems such as the Sketch Engine, that will reach web scalability and avoid inference problems. The main ideas are 1) to augment surface texts (including math formulae) with additional linked representations bearing semantic information (expanded formulae as text, canonicalized text and subformulae) for indexing, including support for indexing structural information (expressed as Content MathML or other tree structures) and 2) use semantic user preferences to order found documents.
Discretionary social network data revelation with a user-centric utility guarantee
Authors: Yi Song, Panagiotis Karras, Sadegh Nobari, Giorgos Cheliotis, Mingqiang Xue, Stéphane Bressan
Venue: CIKM
Year: 2012

The proliferation of online social networks has created intense interest in studying their nature and revealing information of interest to the end user. At the same time, such revelation raises privacy concerns. Existing research addresses this problem following an approach popular in the database community: a model of data privacy is defined, and the data is rendered in a form that satisfies the constraints of that model while aiming to maximize some utility measure. Still, these is no consensus on a clear and quantifiable utility measure over graph data. In this paper, we take a different approach: we define a utility guarantee, in terms of certain graph properties being preserved, that should be respected when releasing data, while otherwise distorting the graph to an extend desired for the sake of confidentiality. We propose a form of data release which builds on current practice in social network platforms: A user may want to see a subgraph of the network graph, in which that user as well as connections and affiliates participate. Such a snapshot should not allow malicious users to gain private information, yet provide useful information for benevolent users. We propose a mechanism to prepare data for user view under this setting. In an experimental study with real data, we demonstrate that our method preserves several properties of interest more successfully than methods that randomly distort the graph to an equal extent, while withstanding structural attacks proposed in the literature.
DTMBIO 2012: international workshop on data and text mining in biomedical informatics
Authors: Min Song, Doheon Lee, Hua Xu, Sophia Ananiadou
Venue: CIKM
Year: 2012

The organizers of ACM Sixth International Workshop on Data and Text Mining in Biomedical Informatics (DTMBIO 12) are happy announce that the sixth DTMBIO will be held in conjunction with CIKM, one of the largest data management conferences. The major interests of DTMBIO are on the state-of-the-art applications of data and text mining on biomedical research problems. DTMBIO 12 will be a forum of discussing and exchanging informatics related techniques and problems in the context of biomedical research.
Demonstrating ProApproX 2.0: a predictive query engine for probabilistic XML
Authors: Asma Souihli, Pierre Senellart
Venue: CIKM
Year: 2012

ProApproX 2.0 allows users to query uncertain tree-structured data in the form of probabilistic XML documents. The demonstrated version integrates a fully redesigned query engine that, first, produces a propositional formula that represents the probabilistic lineage of a given answer over the probabilistic XML document, and, second, searches for an optimal strategy to approximate the probability of the lineage. This latter part relies on a query-optimizer-like approach: exploring different evaluation plans for different parts of the formula and predicting the cost of each plan, using a cost model for the various evaluation algorithms. The demonstration presents the graphical user interface of ProApproX 2.0, that allows a user to input an XPath query and approximation parameters, and lists query results with their probabilities; the interface also gives insight into the way the computation is performed, by displaying the compilation of the query lineage as a tree annotated with evaluation operators.
Segmenting web-domains and hashtags using length specific models
Authors: Sriram Srinivasan, Sourangshu Bhattacharya, Rudrasis Chakraborty
Venue: CIKM
Year: 2012

Segmentation of a string of English language characters into a sequence of words has many applications. Here, we study two applications in the internet domain. First application is the web domain segmentation which is crucial for monetization of broken URLs. Secondly, we propose and study a novel application of twitter hashtag segmentation for increasing recall on twitter searches. Existing methods for word segmentation use unsupervised language models. We find that when using multiple corpora, the joint probability model from multiple corpora performs significantly better than the individual corpora. Motivated by this, we propose weighted joint probability model, with weights specific to each corpus. We propose to train the weights in a supervised manner using max-margin methods. The supervised probability models improve segmentation accuracy over joint probability models. Finally, we observe that length of segments is an important parameter for word segmentation, and incorporate length-specific weights into our model. The length specific models further improve segmentation accuracy over supervised probability models. For all models proposed here, inference problem can be solved using the dynamic programming algorithm. We test our methods on five different datasets, two from web domains data, and three from news headlines data from an LDC dataset. The supervised length specific models show significant improvements over unsupervised single corpus and joint probability models. Cross-testing between the datasets confirm that supervised probability models trained on all datasets, and length specific models trained on news headlines data, generalize well. Segmentation of hashtags result in significant improvement in recall on searches for twitter trends.
Search result presentation based on faceted clustering
Authors: Benno Stein, Tim Gollub, Dennis Hoppe
Venue: CIKM
Year: 2012

We propose a competence partitioning strategy for Web search result presentation: the unmodified head of a ranked result list is combined with a clustering of documents from the result list tail. We identify two principles to which such a clustering must adhere to improve the user's search experience: (1) Avoid the unwanted effect of query aspect repetition, which is called shadowing here. (2) Avoid extreme clusterings, i.e., neither the number of cluster labels nor the number of documents per cluster should exceed the size of the result list head. We present measures to quantify the shadowing effect, and with Faceted Clustering we introduce an algorithm that optimizes the identified principles. The key idea of Faceted Clustering is a dynamic, user-controlled reorganization of a clustering, similar to a faceted navigation system. We report on evaluations using the AMBIENT corpus and demonstrate the potential of our approach by a comparison with two well-known clustering search engines.
Being picky: processing top-k queries with set-defined selections
Authors: Aleksandar Stupar, Sebastian Michel
Venue: CIKM
Year: 2012

Focusing on the top-K items according to a ranking criterion constitutes an important functionality in many different query answering scenarios. The idea is to read only the necessary information---mostly from secondary storage---with the ultimate goal to achieve low latency. In this work, we consider processing such top-K queries under the constraint that the result items are members of a specific set, which is provided at query time. We call this restriction a set-defined selection criterion. Set-defined selections drastically influence the pros and cons of an id-ordered index vs. a score-ordered index. We present a mathematical model that allows to decide at runtime which index to choose, leading to a combined index. To improve the latency around the break even point of the two indices, we show how to benefit from a partitioned score-ordered index and present an algorithm to create such partitions based on analyzing query logs. Further performance gains can be enjoyed using approximate top-K results, with tunable result quality. The presented approaches are evaluated using both real-world and synthetic data.
Simulating prosthetic vision with disortions for retinal prosthesis design
Authors: Mahadevan Subramaniam, Parvathi Chundi, Abhilash Muthuraj, Eyal Margalit, Sylvie Sim
Venue: CIKM
Year: 2012

Retinal prostheses are used to restore vision to individuals with vision impairments caused by the damaged photoreceptors in their retina. Despite the early successes, designing prostheses that can restore functional vision in general, continues to be a challenging problem due to the large number of design parameters that need to be customized for individual users. Gathering data using real patients in a timely and safe manner is also difficult. To address these problems, a virtual environment for realistically and safely simulating prosthetic vision is described. Besides supporting phosphenized rendering of images at different resolutions to normal users, and eye movement tracking, the environment also supports spatial distortions that are commonly perceived by prostheses users. A procedure to automatically generate such spatial distortions is developed. User corrections if any, are logged and compared with the original distortion values to evaluate distortion perception. Experimental results obtained in using this environment to perform various visual acuity tasks are described.
Iterative relevance feedback with adaptive exploration/exploitation trade-off
Authors: Nicolae Suditu, François Fleuret
Venue: CIKM
Year: 2012

Content-based image retrieval systems have to cope with two different regimes: understanding broadly the categories of interest to the user, and refining the search in this or these categories to converge to specific images among them. Here, in contrast with other types of retrieval systems, these two regimes are of great importance since the search initialization is hardly optimal (i.e. the page-zero problem) and the relevance feedback must tolerate the semantic gap of the image's visual features.