OpenRaiser/Intern-Atlas huggingface dataset:
Spatio-temporal association rule mining framework for real-time sensor network applications
Authors: Hamed Chok, Le Gruenwald
Venue: CIKM
Year: 2009

In this paper, we present a data mining framework to estimate missing or corrupted data in sensor network applications - a frequently occurring phenomenon in this domain. The framework is naturally germane to the spatio-temporal analysis of relational data stream evolution. Our method utilizes association rules to capture spatio-temporal correlations in multivariate, dynamically evolving, and unbounded sensor data streams. Existing approaches that tackled this problem do not account for the multi-dimensionality of the node data and their relationship; furthermore they entail simplistic and/or premature assumptions on the temporal and spatial factors to overcome the complexity of the streaming environment. Our technique, called Mining Autonomously Spatio-Temporal Environmental Rules (MASTER), comprehensively formulates the problem of mining patterns in sensor data streams, and yet remains provably adaptive to bounded time and space costs while probabilistically assuring a bounded estimation error. Simulation experiments show MASTER's efficiency in terms of overhead as well as the quality of estimation.
Similarity-aware indexing for real-time entity resolution
Authors: Peter Christen, Ross W. Gayler, David Hawking
Venue: CIKM
Year: 2009

Entity resolution, also known as data matching or record linkage, is the task of identifying and matching records from several databases that refer to the same entities. Traditionally, entity resolution has been applied in batch-mode and on static databases. However, many organisations are increasingly faced with the challenge of having large databases containing entities that need to be matched in real-time with a stream of query records also containing entities, such that the best matching records are retrieved. Example applications include online law enforcement and national security databases, public health surveillance and emergency response systems, financial verification systems, online retail stores, eGovernment services, and digital libraries.
Supporting ranking pattern-based aggregate queries in sequence data cubes
Authors: Chun Kit Chui, Eric Lo, Ben Kao, Wai-Shing Ho
Venue: CIKM
Year: 2009

In recent years, the warehousing and online-analytical processing (OLAP) of archived sequence data have received growing attentions. In particular, the concept of sequence OLAP is recently proposed with the objective of evaluating various kinds of so-called Pattern-Based Aggregate (PBA) queries so that various kinds of data analytical tasks on sequence data can be carried out efficiently. This paper studies the evaluation of ranking PBA queries, which rank the results of PBA queries and return only the top-ranked ones to users. We discuss how ranking PBA queries drastically improve the usability of S-OLAP systems and present techniques that can evaluate various kinds of ranking PBA queries efficiently.
A web-based comparative visualization system for human endogenous RetroVirus(HERV) on whole genomes
Authors: Woo-Keun Chung, Hyong-Jun Kim, Hwan-Gue Cho
Venue: CIKM
Year: 2009

Human Endogenous RetroViruses(HERVs) are suggested that they have a function of regulating the activity of human genes and could produce protein in some conditions. So it is crucial to examine the physical layout relationship between HERVs and genes in the whole genome scale. In this paper we present RetroScope, a new Web-based comparative visualization system for HERV over 4 whole primate genomes including Human, Chimpanzee, Orangutan and Rhesus monkey. So RetroScope enables us to find the retro element which is very close to a specified gene in the form of exonoverlapping or promotor, primer overlapping. Thus our system enables biologist to provide global understanding by comparing the linear configuration of several HERVs in the whole chromosome scales by using a fast HERV alignment algorithm. Also by alignment of HERVs, we can find the most similar pair of chromosomes with respect to the configuration of HERV elements, which would be another clues to construct phylogenetics based on HERV. RetroScope is available on http://neobio.cs.pusan.ac.kr/sretroscope/.
Retrieval constraints and word frequency distributions: a log-logistic model for IR
Authors: Stéphane Clinchant, Éric Gaussier
Venue: CIKM
Year: 2009

We first present in this paper an analytical view of heuristic retrieval constraints which yields simple tests to determine whether a retrieval function satisfies the constraints or not. We then review empirical findings on word frequency distributions and the central role played by burstiness in this context. This leads us to propose a formal definition of burstiness which can be used to characterize probability distributions wrt this phenomenon. We then introduce the family of information-based IR models which naturally captures heuristic retrieval constraints when the underlying probability distribution is bursty and propose a new IR model within this family, based on the log-logistic distribution. The experiments we conduct on three different collections illustrate the good behavior of the log-logistic IR model: it significantly outperforms the Jelinek-Mercer and Dirichlet prior language models on all three collections, with both short and long queries and for both the MAP and the precision at 10 documents. It also outperforms the InL2 DFR model for the MAP, and yields results on a par with it for the precision at 10.
Linear inclusion for XML regular expression types
Authors: Dario Colazzo, Giorgio Ghelli, Luca Pardini, Carlo Sartiani
Venue: CIKM
Year: 2009

Type inclusion is a fundamental operation in every type-checking compiler, but it is quite expensive for XML manipulation languages. We recently presented an inclusion checking algorithm for an expressive family of XML type languages which is polynomial, but runs in quadratic time both in the best and in the worst cases. We present here an algorithm that has a linear-time backbone, and resorts to the quadratic approach for some specific parts of the compared types. Our experiments show that the new algorithm typically runs in linear time, hence can be used as a building block for a practical type-checking compiler.
Efficient computation of impact degrees for multiple reactions in metabolic networks with cycles
Authors: Yang Cong, Takeyuki Tamura, Tatsuya Akutsu, Wai-Ki Ching
Venue: CIKM
Year: 2009

Analysis of the robustness of a metabolic network against of single or multiple reaction(s) is useful for mining important enzymes/genes. For that purpose, the impact degree was proposed by Jiang et al. In this short paper, we extend the impact degree for metabolic networks containing cycles and develop a simple algorithm for its computation. Furthermore, we propose an improved algorithm for computing impact degrees for deletions of multiple reactions. The results of preliminary computational experiments suggest that the improved algorithm is several tens of times faster than a simple algorithm.
RS-Wrapper: random write optimization for solid state drive
Authors: Da Zhou, Xiaofeng Meng
Venue: CIKM
Year: 2009

Solid State Drive (SSD), emerging as new data storage media with high random read speed, has been widely used in laptops, desktops, and data servers to replace hard disk during the past few years. However, poor random write performance becomes the bottle neck in practice. In this paper, we propose to insert unmodified data into random write sequence in order to convert random writes into sequential writes, and thus data sequence can be flushed at the speed of sequential write. Further, we propose a clustering strategy to improve the performance by reducing quantity of unmodified data to read. After exploring the intrinsic parallelism of SSD, we also propose to flush write sequences with the help of the simultaneous program between planes and parallel program between devices for the first time. Comprehensive experiments show that our method outperform the existing random-write solution up to one order of magnitude improvement.
Vetting the links of the web
Authors: Na Dai, Brian D. Davison
Venue: CIKM
Year: 2009

Many web links mislead human surfers and automated crawlers because they point to changed content, out-of-date information, or invalid URLs. It is a particular problem for large, well-known directories such as the dmoz Open Directory Project, which maintains links to representative and authoritative external web pages within their various topics. Therefore, such sites involve many editors to manually revisit and revise links that have become out-of-date. To remedy this situation, we propose the novel web mining task of identifying outdated links on the web. We build a general classification model, primarily using local and global temporal features extracted from historical content, topic, link and time-focused changes over time. We evaluate our system via five-fold cross-validation on more than fifteen thousand ODP external links selected from thirteen top-level categories. Our system can predict the actions of ODP editors more than 75% of the time. Our models and predictions could be useful for various applications that depend on analysis of web links, including ranking and crawling.
Incremental similarity joins with edit distance constraints
Authors: Dongbo Dai, Gang Zhao
Venue: CIKM
Year: 2009

With the dynamic increase of string data and the need to integrate data from multiple data sources, a challenging issue is to perform similarity joins on dynamically-augmented string sets. Existing methods only exploit domain-oriented filters to speed up join processing on static datasets, which are inefficient for incremental data-generation scenarios.
A translation model for matching reviews to objects
Authors: Nilesh N. Dalvi, Ravi Kumar, Bo Pang, Andrew Tomkins
Venue: CIKM
Year: 2009

We develop a generic method for the review matching problem, which is to match unstructured text reviews to a list of objects, where each object has a set of attributes. To this end, we propose a translation model for generating reviews from a structured description of objects. We develop an EM-based method to estimate the model parameters and use this model to find, given a review, the object most likely to be the topic of the review. We conduct extensive experiments on two large-scale datasets: a collection of restaurant reviews from Yelp and a collection of movie reviews from IMDb. The experiments show that our translation model-based method is superior to traditional tf-idf based methods as well as a recent mixture model-based method for the review matching problem.
Automatic retrieval of similar content using search engine query interface
Authors: Ali Dasdan, Paolo D&apos, Alberto, Santanu Kolay, Chris Drome
Venue: CIKM
Year: 2009

We consider the coverage testing problem where we are given a document and a corpus with a limited query interface and asked to find if the corpus contains a near-duplicate of the document. This problem has applications in search engines for competitive coverage testing. To solve this problem, we propose approaches that work in three main steps: generate a query signature from the document, query the corpus using the query signature and scrape the returned results, and validate the similarity between the input document and the returned results. We discuss techniques to control and bound the performance of these methods. We perform large-scale experimental validation and show that these methods perform well across different search engine corpora and documents in multiple languages. They also are robust against performance parameter variations.
CAOFES: an ontological framework for web service retrieval
Authors: Sourish Dasgupta, Satish Bhat, Yugyung Lee
Venue: CIKM
Year: 2009

Semantic web search involves retrieval of user-specific web artifacts by utilizing their semantic descriptions. A very specific web artifact that has evolved in recent times is web services. Web services can be semantically described in languages like OWL-S. However, such languages are limited with respect to their expressivity of context. They also lack a formal ontological framework where efficient web service retrieval can be conducted. In this paper we model a service request scenario within the web as an event-driven system. Services as well as user requests are modeled as events. We propose an ontological framework called Context-Aware Ontology Framework for Events and Services (CAOFES) where such event-driven web service retrieval can be efficiently executed by a novel reasoning technique.
Enhancing expertise retrieval using community-aware strategies
Authors: Hongbo Deng, Irwin King, Michael R. Lyu
Venue: CIKM
Year: 2009

Expertise retrieval has received increased interests in recent years, whose task is to suggest people with relevant expertise. Motivated by the observation that communities could provide valuable insight and distinctive information, we investigate two community-aware strategies to enhance expertise retrieval. We first propose a new smoothing method using the community context instead of the whole collection for statistical language model in the document-based model. Furthermore, a query-sensitive AuthorRank is proposed to model the authors' authorities according to the community co-authorship networks, and then an adaptive ranking refinement method is developed to further enhance expertise retrieval. Experimental results demonstrate the effectiveness and robustness of both community-aware strategies.
POkA: identifying pareto-optimal k-anonymous nodes in a domain hierarchy lattice
Authors: Rinku Dewri, Indrajit Ray, Indrakshi Ray, L. Darrell Whitley
Venue: CIKM
Year: 2009

Data generalization is widely used to protect identities and prevent inference of sensitive information during the public release of microdata. The k-anonymity model has been extensively applied in this context. The model seeks a generalization scheme such that every individual becomes indistinguishable from at least k-1 other individuals and the loss in information while doing so is kept at a minimum. The search is performed on a domain hierarchy lattice where every node is a vector signifying the level of generalization for each attribute. An effort to understand privacy and data utility trade-offs will require knowing the minimum possible information losses of every possible value of k. However, this can easily lead to an exhaustive evaluation of all nodes in the hierarchy lattice. In this paper, we propose using the concept of Pareto-optimality to obtain the desired trade-off information. A Pareto-optimal generalization is one in which no other generalization can provide a higher value of k without increasing the information loss. We introduce the Pareto-Optimal k-Anonymization (POkA) algorithm to traverse the hierarchy lattice and show that the number of node evaluations required to find the Pareto-optimal generalizations can be significantly reduced. Results on a benchmark data set show that the algorithm is capable of identifying all Pareto-optimal nodes by evaluating only 20% of nodes in the lattice.
SOIRE: a service-oriented IR evaluation architecture
Authors: Michael Dittenbach, Bernhard Pflugfelder, Andreas Pesenhofer, Giovanna Roda, Helmut Berger
Venue: CIKM
Year: 2009

We have developed a system that offers comprehensive analysis functionality for information retrieval experiments combined with a storage facility for persisting experiment data in a uniform fashion to facilitate repeatability and comparability of experiments. Our Service-Oriented IR Evaluation Framework - SOIRE offers a number of technological interfaces based on open networking standards and modeling languages to connect to other systems while regarding ease-of-use for researchers as the feature of utmost importance.
Weighted network decapitation: the economics of iterated attack and defense
Authors: Josep Domingo-Ferrer
Venue: CIKM
Year: 2009

Vulnerability of networks (e.g. peer-to-peer networks, social networks, etc.) against one-shot decapitation attacks has been addressed several times in the literature. A first study on how a network can best defend itself by replenishing nodes and rewiring edges after decapitation was made by Nagaraja and Anderson. We extend the work of those authors by: i) considering weighted networks; ii) taking into account the economic aspects of the attack and defense strategies, namely the cost of node destruction/replenishment and subtler costs such as the average path length increase or the privacy degradation.
Multidimensional routing indices for efficient distributed query processing
Authors: Christos Doulkeridis, Akrivi Vlachou, Kjetil Nørvåg, Yannis Kotidis, Michalis Vazirgiannis
Venue: CIKM
Year: 2009

Traditional routing indices in peer-to-peer (P2P) networks are mainly designed for document retrieval applications and maintain aggregated one-dimensional values representing the number of documents that can be obtained in a certain direc-tion in the network. In this paper, we introduce the concept of multidimensional routing indices (MRIs), which are suit-able for handling multidimensional data represented by min-imum bounding regions (MBRs). Depending on data distri-bution on peers, the aggregation of the MBRs may lead to MRIs that exhibit extremely poor performance, which ren-ders them ineffective. Thus, focusing on a hybrid unstruc-tured P2P network, we analyze the parameters for building MRIs of high selectivity. We present techniques that boost the query routing performance by detecting similar peers and grouping and reassigning these peers to other parts of the hybrid network in a distributed and scalable way. We demonstrate the advantages of our approach using large-scale simulations.
A query language for analyzing networks
Authors: Anton Dries, Siegfried Nijssen, Luc De Raedt
Venue: CIKM
Year: 2009

With more and more large networks becoming available, mining and querying such networks are increasingly important tasks which are not being supported by database models and querying languages. This paper wants to alleviate this situation by proposing a data model and a query language for facilitating the analysis of networks. Key features include support for executing external tools on the networks, flexible contexts on the network each resulting in a different graph, primitives for querying subgraphs (including paths) and transforming graphs.
Building domain-oriented sentiment lexicon by improved information bottleneck
Authors: Weifu Du, Songbo Tan
Venue: CIKM
Year: 2009

This paper describes an adapted information bottleneck approach for construction of domain-oriented sentiment lexicon. The basic idea is to use three kinds of relationships (WWinter, WDinter and WDintra,) to infer the semantic orientation of the out-of-domain words. The experimental results demonstrate that proposed method could dramatically improve the accuracy of the baseline approach on the construction of out-of-domain sentiment lexicon.
Community mining on dynamic weighted directed graphs
Authors: Dongsheng Duan, Yuhua Li, Yanan Jin, Zhengding Lu
Venue: CIKM
Year: 2009

This paper focuses on community mining including community discovery and change-point detection on dynamic weighted directed graphs(DWDG). Real networks such as e-mail, co-author and financial networks can be modeled as DWDG. Community mining on DWDG has not been studied thoroughly, although that on static(or dynamic undirected unweighted)graphs has been exploited extensively. In this paper, Stream-Group is proposed to solve community mining on DWDG. For community discovery, a two-step approach is presented to discover the community structure of a weighted directed graph(WDG) in one time-slice: (1)The first step constructs compact communities according to each node's single compactness which indicates the degree of a node belonging to a community in terms of the graph's relevance matrix; (2)The second step merges compact communities along the direction of maximum increment of the modularity. For change-point detection, a measure of the similarity between partitions is presented to determine whether a change-point appears along the time axis and an incremental algorithm is presented to update the partition of a graph segment when adding a new arriving graph into the graph segment. The effectiveness and efficiency of our algorithms are validated by experiments on both synthetic and real networks. Results show that our algorithms have a good trade-off between the effectiveness and efficiency in discovering communities and change-points.
(Not) yet another matcher
Authors: Fabien Duchateau, Remi Coletta, Zohra Bellahsene, Renée J. Miller
Venue: CIKM
Year: 2009

Discovering correspondences between schema elements is a crucial task for data integration. Most schema matching tools are semi-automatic, e.g. an expert must tune some parameters (thresholds, weights, etc.). They mainly use several methods to combine and aggregate similarity measures. However, their quality results often decrease when one requires to integrate a new similarity measure or when matching particular domain schemas. This paper describes YAM (Yet Another Matcher), which is a schema matcher factory. Indeed, it enables the generation of a dedicated matcher for a given schema matching scenario, according to user inputs. Our approach is based on machine learning since schema matchers can be seen as classifiers. Several bunches of experiments run against matchers generated by YAM and traditional matching tools show how our approach is able to generate the best matcher for a given scenario.
YAM: a schema matcher factory
Authors: Fabien Duchateau, Remi Coletta, Zohra Bellahsene, Renée J. Miller
Venue: CIKM
Year: 2009

In this paper, we present YAM, a schema matcher factory. YAM (Yet Another Matcher) is not (yet) another schema matching system as it enables the generation of a la carte schema matchers according to user requirements. These requirements include a preference for recall or precision, a training data set (schemas already matched) and provided expert correspondences. YAM uses a knowledge base that includes a (possibly large) set of similarity measures and classifiers. Based on the user requirements, YAM learns how to best apply these tools (similarity measures and classifiers) in concert to achieve the best matching quality. In our demonstration, we will let users apply YAM to build the best schema matcher for different user requirements.
A proactive personalised retrieval system
Authors: Desmond Elliott, Joemon M. Jose
Venue: CIKM
Year: 2009

We present a personalised retrieval system that captures explicit relevance feedback to build an evolving user profile with multiple aspects. The user profile is used to proactively retrieve results between search sessions to support multi-session search tasks. This approach to supporting users with their multi-session search tasks is evaluated in a between-subjects multiple time-series study with ten subjects performing two simulated work situation tasks over five sessions. System interaction data shows that subjects using the personalised retrieval system issue fewer queries and interact with fewer results than subjects using a baseline system. The interaction data also shows a trend of subjects interacting with the proactively retrieved results in the personalised retrieval system.