OpenRaiser/Intern-Atlas huggingface dataset:
Key blog distillation: ranking aggregates
Authors: Craig Macdonald, Iadh Ounis
Venue: CIKM
Year: 2008

Searchers on the blogosphere often have a need to identify other key bloggers with similar interests to their own. However, a main difference of this blog distillation task from normal adhoc or Web document retrieval is that each blog can be seen as an aggregate of its constituent posts. On the other hand, we show that the task is similar to the expert search task, where a person's expertise is derived from the aggregate of their publications or emails. In this paper, we investigate several aspects of blog retrieval: Firstly, we experiment whether a blog should be represented as a whole unit, or as by considering each of its posts as indicators of its relevance, showing that expert search techniques can be adapted for blog search; Secondly, we examine whether indexing only the XML feed provided by each blog (and which is often incomplete) is sufficient, or whether the full-text of each blog post should be downloaded; Lastly, we use approaches to detect the central or recurring interests of each blog to increase the retrieval effectiveness of the system. Using the TREC 2007 Blog dataset, the results show that our proposed expert search paradigm is indeed useful in identifying key bloggers, achieving high retrieval effectiveness.
Identification of gene function using prediction by partial matching (PPM) language models
Authors: Malika Mahoui, William John Teahan, Arvind Kumar Thirumalaiswamy Sekhar, Satyasaibabu Chilukuri
Venue: CIKM
Year: 2008

In this paper, we describe the utilization of text encoding and prediction by partial matching language modeling to identify gene functions within abstracts of biomedical papers. The National Center for Biotechnology Information has "GeneRIF" - a collection of the best possible functional representations for a subset of abstracts from PubMed. We use GeneRIF to test the efficiency of our technique. We discuss the methodology adopted to construct models necessary to enable the Text Mining Toolkit to distinguish between gene functions and the rest of the abstract (non gene functions). We also describe the similarity based approach we deploy on the list of automatically annotated functions to generate the most likely gene function representative of the paper. The results indicate that our combined approach to identify gene functions in scientific abstracts performs very well on both precision and recall, and therefore presents exciting opportunities for use in extracting other entities embedded in scientific text.
Nested region algebra extended with variables for tag-annotated text search
Authors: Katsuya Masuda, Jun&apos, ichi Tsujii
Venue: CIKM
Year: 2008

This paper presents a framework for searching text regions with specifying annotated information in tag-annotated text by using Region Algebra. We extend the efficient algorithm for region algebra to handle both nested and crossed regions and introduce variables for attribute values to treat tag-annotations in which attributes indicate another tag regions. Our framework have been implemented in a text search engine for MEDLINE, which is a large textbase of abstracts in medical science. Experiments in tag-annotated MEDLINE abstracts demonstrate the effectiveness of specifying annotations and the efficiency of our framework.
Fault-tolerant semantic mappings among heterogeneous and distributed local ontologies
Authors: Abdul-Rahman Mawlood-Yunis
Venue: CIKM
Year: 2008

Overcoming semantic mapping faults, i.e. semantic incompatibility, is a vital issue for the success of semantic-based peer-to-peer systems. There are various research efforts which address the classification and the resolution of the semantic mapping fault problem, i.e. translation errors. All of the precedent research related to semantic mapping faults demonstrates one significant shortcoming. This flaw is the inability to discriminate between non-permanent and permanent semantic mapping faults, i.e. how long do semantic incompatibilities stay effective and are the semantic incompatibilities permanent or temporary? The current research examines the destructive effect of semantic mapping faults on the Emerging Semantics, i.e. bottom-up construction of ontology and proposes a solution to detect temporal semantic mapping faults. The current research also demonstrates that fault-tolerant semantic mapping will result in Emerging Semantics which are more complete and agreeable than those domain ontologies that are built without consideration for fault-tolerant semantic mapping.
Generalized inverse document frequency
Authors: Donald Metzler
Venue: CIKM
Year: 2008

Inverse document frequency (IDF) is one of the most useful and widely used concepts in information retrieval. There have been various attempts to provide theoretical justifications for IDF. One of the most appealing derivations follows from the Robertson-Sparck Jones relevance weight. However, this derivation, and others related to it, typically make a number of strong assumptions that are often glossed over. In this paper, we re-examine these assumptions from a Bayesian perspective, discuss possible alternatives, and derive a new, more generalized form of IDF that we call generalized inverse document frequency. In addition to providing theoretical insights into IDF, we also undertake a rigorous empirical evaluation that shows generalized IDF outperforms classical versions of IDF on a number of ad hoc retrieval tasks.
An integration strategy for mining product features and opinions
Authors: Qingliang Miao, Qiudan Li, Ruwei Dai
Venue: CIKM
Year: 2008

With the development of Web 2.0, the web has become an extremely valuable source for mining opinions. In this paper, we study how to automatically mine product features and opinions by integrating multiple review sources. We propose an integration strategy to solve the problem. Experiments show that the proposed strategy is effective.
Anomaly-free incremental output in stream processing
Authors: George A. Mihaila, Ioana Stanoi, Christian A. Lang
Venue: CIKM
Year: 2008

Continuous queries enable alerts, predictions, and early warning in various domains such as health care, business process monitoring, financial applications, and environment protection. Currently, the consistency of the result cannot be assessed by the application, since only the query processor has enough internal information to determine when the output has reached a consistent state. To our knowledge, this is the first paper that addresses the problem of consistency under the assumptions and constraints of a continuous query model. In addition to defining an appropriate consistency notion, we propose techniques for guaranteeing consistency. We implemented the proposed techniques in our existing stream engine, and we report on the characteristics of the observed performance. As we show, these methods are practical as they impose only a small overhead on the system.
Learning to link with wikipedia
Authors: David N. Milne, Ian H. Witten
Venue: CIKM
Year: 2008

This paper describes how to automatically cross-reference documents with Wikipedia: the largest knowledge base ever known. It explains how machine learning can be used to identify significant terms within unstructured text, and enrich it with links to the appropriate Wikipedia articles. The resulting link detector and disambiguator performs very well, with recall and precision of almost 75%. This performance is constant whether the system is evaluated on Wikipedia articles or "real world" documents.
SNIF TOOL: sniffing for patterns in continuous streams
Authors: Abhishek Mukherji, Elke A. Rundensteiner, David C. Brown, Venkatesh Raghavan
Venue: CIKM
Year: 2008

Continuous time-series sequence matching, specifically, matching a numeric live stream against a set of redefined pattern sequences, is critical for domains ranging from fire spread tracking to network traffic monitoring. While several algorithms exist for similarity matching of static time-series data, matching continuous data poses new, largely unsolved challenges including online real-time processing requirements and system resource limitations for handling infinite streams. In this work, we propose a novel live stream matching framework, called n-Snippet Indices Framework (in short, SNIF), to tackle these challenges. SNIF employs snippets as the basic unit for matching streaming time-series. The insight is to perform the matching at two levels of granularity: bag matching of subsets of snippets of the live stream against prefixes of the patterns, and order checking for maintaining successive candidate snippet bag matches. We design a two-level index structure, called SNIF index, which supports these two modes of matching. We propose a family of online two-level prefix matching algorithms that trade off between result accuracy and response time. The effectiveness of SNIF to detect patterns has been thoroughly tested through experiments using real datasets from the domains of fire monitoring and sensor motes. In this paper, we also present a study of SNIF's performance, accuracy and tolerance to noise compared against those of the state-of-the-art Continuous Query with Prediction (CQP) approach.
Efficient and effective link analysis with precomputed salsa maps
Authors: Marc Najork, Nick Craswell
Venue: CIKM
Year: 2008

SALSA is a link-based ranking algorithm that takes the result set of a query as input, extends the set to include additional neighboring documents in the web graph, and performs a random walk on the induced subgraph. The stationary probability distribution of this random walk, used as a relevance score, is significantly more effective for ranking purposes than popular query-independent link-based ranking algorithms such as PageRank. Unfortunately, this requires significant effort at query-time, to access the link graph and compute the stationary probability distribution. In this paper, we explore whether it is possible to perform most of the computation off-line, prior to the arrival of any queries. The off-line phase of our approach computes a "score map" for each node in the web graph by performing a SALSA-like algorithm on the neighborhood of that node and retaining the scores of the most promising nodes in the neighborhood graph. The on-line phase takes the results to a query, retrieves the score map of each result, and returns for each result a score that is the sum of the matching scores from each score map. We evaluated this algorithm on a collection of about 28,000 queries with partially labeled results, and found that it is significantly more effective than PageRank, although not quite as effective as SALSA. We also studied the trade-off between ranking effectiveness and space requirements.
Identification of temporal association rules from time-series microarray data set: temporal association rules
Authors: Hojung Nam, Ki Young Lee, Doheon Lee
Venue: CIKM
Year: 2008

One of the most challenging problems in mining gene expression data is to identify how the expression of any particular gene affects the expression of other genes. To elucidate the relationships between genes, an association rule mining (ARM) method has been applied to microarray gene expression data. A conventional ARM method, however, has a limit on extracting temporal dependencies between genes, though the temporal information is indispensable to discover underlying regulation mechanisms in biological pathways. In this paper, therefore, we propose a novel method, referred to as temporal association rule mining (TARM), which can extract temporal dependencies among related genes. A temporal association rule has the form [gene A ↑, gene B↓] → (7 min)[gene C], which represents that high expression level of gene A and significant repression of gene B followed by significant expression of gene C after 7 minutes. The proposed TARM method is tested with Saccharomyces cerevisiae cell cycle time-series microarray gene expression data set. In the parameter fitting phase of TARM, the best parameter set [threshold = ±0.8, support cutoff = 3 transactions, confidence cutoff = 90%], which extracted the most number of correct associations in KEGG cell cycle pathway, has been chosen for rule mining phase. Furthermore, comparing the precision scores of TARM (0.38) and Bayesian network (0.16), TARM method showed better accuracy. With the best parameter set, numbers of temporal association rules with five transcriptional time delays (0, 7, 14, 21, 28 minutes) are extracted from gene expression data of 799 genes which are pre-identified cell cycle relevant genes, while comparably small number of rules are extracted from random shuffled gene expression data of 799 genes. From the extracted temporal association rules, associated genes which play same role of biological processes within short transcriptional time delay and some temporal dependencies between genes with specific biological processes are identified.
Fast correlation analysis on time series datasets
Authors: Philon Nguyen, Nematollaah Shiri
Venue: CIKM
Year: 2008

There has been increasing interest for efficient techniques for fast correlation analysis of time series data in different application domains. We present three algorithms for (1) bivariate correlation queries, (2) multivariate correlation queries, and (3) correlation queries based on a new correlation measure we introduce using dynamic time warping. To support these algorithms, we use a variant of the Compact Multi-Resolution Index (CMRI). In addition to conventional nearest neighbor and range queries supported by CMRI, the proposed algorithms compute all answers to user-defined, ad hoc and parametric correlation queries. The results of our experiments indicate a speed-up of two orders of magnitude over the brute force algorithm, and an order of magnitude improvement on average, while offering more functionalities than provided by existing techniques such as StatStream and the Spatial Cone Tree.
Polyhedral transformation for indexed rank order correlation queries
Authors: Philon Nguyen, Nematollaah Shiri
Venue: CIKM
Year: 2008

Rank order correlation has been used extensively when the data is non-parametric or when the relationship between two variables is nonlinear and monotonic. In such cases, linear correlation measures, such as the product-moment coefficient, are inadequate and fail to detect correlative relations. We present a polyhedral indexing technique for rank order correlation queries for time series data. We use an interesting geometry interpretation of rank order correlation which lends itself to indexing by spatial indexes such as R-trees. Our experimental results indicate one to two orders of magnitudes improvement over sequential scan - the only alternative solution.
Adaptive distributed indexing for structured peer-to-peer networks
Authors: Linh Thai Nguyen, Wai Gen Yee, Ophir Frieder
Venue: CIKM
Year: 2008

Structured peer-to-peer networks support keyword search by building a distributed index over the collective content shared by all peers. Building the index and processing queries involve data transfer among peers, thus it is important to keep both of these activities bandwidth-efficient. However, this goal is difficult to attain, as smaller, less precise indices reduce index building and access costs but increase query processing cost, which potentially increases overall cost. We study the trade-off between indexing cost and query processing cost in a structured peer-to-peer network and propose a cost-reducing, adaptive, distributed indexing technique based on the term distributions in local shared contents and user query logs. Using this information, we reduce costs by tuning the precision of the index. The approach we take is to group local documents and to index the groups instead of either individual documents or entire peer collections. We control total cost by controlling the number and contents of groups. We propose a probabilistic model to estimate the cost of grouping, which allows us to identify the optimal number of groups to be created. In addition, we propose a cost-based distance function to guide the document grouping process. Experimental results show that our adaptive indexing technique reduces cost by up to 47% compared with peer-level grouping and by up to 73% compared with document-level grouping.
Group-based learning: a boosting approach
Authors: Weijian Ni, Jun Xu, Hang Li, Yalou Huang
Venue: CIKM
Year: 2008

This paper points out that many machine learning problems in IR should be and can be formalized in a novel way, referred to as 'group-based learning'. In group-based learning, it is assumed that training data as well as testing data consist of groups. The classifier is created and utilized across groups. Furthermore, evaluation in testing and also in training are conducted at group level, with the use of evaluation measures defined on a group. This paper addresses the problem and presents a Boosting algorithm to perform the new learning task. The algorithm, referred to as AdaBoost.Group, is proved to be able to improve accuracies in terms of group-based measures during training.
Natural language retrieval of grocery products
Authors: Petteri Nurmi, Eemil Lagerspetz, Wray L. Buntine, Patrik Floréen, Joonas Kukkonen, Peter Peltonen
Venue: CIKM
Year: 2008

In this paper we describe modifications to a natural language grocery retrieval system, introduced in our earlier work. We also compare our system against an off-the-shelf retrieval tool, and show that our system is significantly better for top-ranked retrieval results.
Similarity cross-analysis of tag / co-tag spaces in social classification systems
Authors: Steffen Oldenburg, Martin Garbe, Clemens H. Cap
Venue: CIKM
Year: 2008

Recent growth of social classification systems due to steadily increasing popularity has established a multitude of heterogeneous isolated, non-integrated, and non-interoperable tag spaces. Contrary to current research predominantly focusing on single folksonomies, we exploit cross-space similarities to improve a variety of tagging use cases beyond the limits of one folksonomy. This paper presents the results of practical studies concerning cross-space analysis of (co-)tag spaces of five well-established social classification services for tagging of bookmarks (del.icio.us, BibSonomy bookmarks), and publications (BibSonomy publications, CiteULike, Connotea). The studies are based on one month data sets of RSS recent feeds from the same time scope. We provide a profound motivation for cross-space tagging, and give insight into similarities and intersections of (top ranking) (co-)tag spaces as well as convergence aspects over time.
Corrupted queries in Spanish text retrieval: error correction vs. N-Grams
Authors: Juan Otero, Jesús Vilares, Manuel Vilares Ferro
Venue: CIKM
Year: 2008

In this paper, we propose and evaluate two different alternatives to deal with degraded queries on Spanish IR applications. The first one is an n-gram-based strategy which has no dependence on the degree of available linguistic knowledge. On the other hand, we propose two spelling correction techniques, one of which has a strong dependence on a stochastic model that must be previously built from a POS-tagged corpus. In order to study their validity, a testing framework has been formally designed and applied on both approaches.
Utilization of navigational queries for result presentation and caching in search engines
Authors: Rifat Ozcan, Ismail Sengör Altingövde, Özgür Ulusoy
Venue: CIKM
Year: 2008

We propose result page models with varying granularities for navigational queries and show that this approach provides a better utilization of cache space and reduces bandwidth requirements.
Issues in searching for Indian language web content
Authors: Dipasree Pal, Prasenjit Majumder, Mandar Mitra, Sukanya Mitra, Aparajita Sen
Venue: CIKM
Year: 2008

This paper looks at the problem of searching for Indian language (IL) content on the Web. Even though the amount of IL content that is available on the Web is growing rapidly, searching through this content using the most popular websearch engines poses certain problems. Since the popular search engines do not use any stemming / orthographic normalization for Indian languages, recall levels for IL searches can be low. We provide some examples to indicate the extent of this problem, and suggest a simple and efficient solution to the problem.
Indexing and retrieval of a Greek corpus
Authors: Georgios Paltoglou, Michail Salampasis, Fotis Lazarinis
Venue: CIKM
Year: 2008

Greek is one of the most difficult languages to handle in Web Information Retrieval (IR) related tasks. Its difficulty stems from the fact that it is grammatically, morphologically and orthographically more complex than the lingua franca of IR, English. In this paper, we address a significant number of issues that originate from the Greek language. We use a number of techniques to determine the correct encoding that is used by web pages written in Greek. We test the effect of using a Greek stopword list in a realistic and controlled Web environment. We employ a character mapping scheme, in order to overcome the problem of the diversity of diacritics used in the language, such as accents and diaeresis. We utilize word distance and fuzzy similarity metrics in order to make up for the different forms that nouns, verbs and articles appear because of conjugations and inflections and additionally handle greeklish queries, a transliterated form of Greek. The conducted experiments present some effective ways to increase the accuracy in Greek IR tasks.
Integral based source selection for uncooperative distributed information retrieval environments
Authors: Georgios Paltoglou, Michail Salampasis, Maria Satratzemi
Venue: CIKM
Year: 2008

In this paper, a new source selection algorithm for uncooperative distributed information retrieval environments is presented. The algorithm functions by modeling each information source as an integral, using the relevance score and the intra-collection position of its sampled documents in reference to a centralized sample index and selects the collections that cover the largest area in the rank-relevance space. Based on the above novel metric, the algorithm explicitly focuses on addressing the two goals of source selection; high recall which is important for source recommendation applications and high precision aiming to produce a high precision final merged list. For the latter goal in particular, the new approach steps away from the usual practice of DIR systems of explicitly declaring the number of collections that must be queried and instead receives as input only the number of retrieved documents in the final merged list, dynamically calculating the number of collections that are selected and the number of documents requested from each. The algorithm is tested in a wide range of testbeds in both recall and precision oriented settings and its effectiveness is found to be equal or better than other state-of-the-art algorithms.
Protecting location privacy against location-dependent attack in mobile services
Authors: Xiao Pan, Jianliang Xu, Xiaofeng Meng
Venue: CIKM
Year: 2008

Privacy preservation has recently received considerable attention for location-based mobile services. In this paper, we present location-dependent attack resulting from continuous and dependent location updates and propose an incremental clique-based cloaking algorithm, called ICliqueCloak, to defend against location-dependent attack. The main idea is to incrementally maintain maximal cliques for location cloaking in an un-directed graph that takes into consideration the effect of continuous location updates.