OpenRaiser/Intern-Atlas huggingface dataset:
Efficient web matrix processing based on dual reordering
Authors: Chih-Ming Hsu, Ming-Syan Chen
Venue: CIKM
Year: 2008

PageRank is one of the most important ranking techniques used in search engines nowadays. Since billions of pages already existed in Web, many PageRank acceleration techniques were explored by many researchers. However, in the real Web, just like the existence of pages without out-links, there are many pages without in-links. (In this paper, a Web page without in-links is called a reverse-dangling page.) Given the state of the art, we propose a new reordered PageRank algorithm, called two-way reordered PageRank algorithm, which exploits both dangling nodes and reverse-dangling nodes to reduce the computational complexity of the PageRank vector.
Error-driven generalist+experts (edge): a multi-stage ensemble framework for text categorization
Authors: Jian Huang, Omid Madani, C. Lee Giles
Venue: CIKM
Year: 2008

We introduce a multi-stage ensemble framework, Error-Driven Generalist+Expert or Edge, for improved classification on large-scale text categorization problems. Edge first trains a generalist, capable of classifying under all classes, to deliver a reasonably accurate initial category ranking given an instance. Edge then computes a confusion graph for the generalist and allocates the learning resources to train experts on relatively small groups of classes that tend to be systematically confused with one another by the generalist. The experts' votes, when invoked on a given instance, yield a reranking of the classes, thereby correcting the errors of the generalist. Our evaluations showcase the improved classification and ranking performance on several large-scale text categorization datasets. Edge is in particular efficient when the underlying learners are efficient. Our study of confusion graphs is also of independent interest.
A latent variable model for query expansion using the hidden markov model
Authors: Qiang Huang, Dawei Song
Venue: CIKM
Year: 2008

We propose a novel probabilistic method based on the Hid-\nden Markov Model (HMM) to learn the structure of a Latent\nVariable Model (LVM) for query language modeling. In the\nproposed LVM, the combinations of query terms are viewed\nas the latent variables and the segmented chunks from the\nfeedback documents are used as the observations given these\nlatent variables. Our extensive experiments shows that our\nmethod significantly outperforms a number of strong base-\nlines in terms of both effectiveness and robustness.
Achieving both high precision and high recall in near-duplicate detection
Authors: Lian&apos, en Huang, Lei Wang, Xiaoming Li
Venue: CIKM
Year: 2008

To find near-duplicate documents, fingerprint-based paradigms such as Broder's shingling and Charikar's simhash algorithms have been recognized as effective approaches and are considered the state-of-the-art. Nevertheless, we see two aspects of these approaches which may be improved. First, high score under these algorithms' similarity measurement implies high probability of similarity between documents, which is different from high similarity of the documents. But how similar two documents are is what we really need to know. Second, there has to be a tradeoff between hash-code length and hash-code multiplicity in fingerprint paradigms, which makes it hard to maintain a satisfactory recall level while improving precision.
Peer production of structured knowledge -: an empirical study of ratings and incentive mechanisms
Authors: Christian Hütter, Conny Kühne, Klemens Böhm
Venue: CIKM
Year: 2008

Creating and maintaining semantic structures such as ontologies on a large scale is a labor-intensive task, which a sole individual cannot perform. Established automated solutions for this task do not yet exist. Peer production is a promising approach to create structured knowledge: Members of an online community create and maintain semantic structures collaboratively. To motivate members to participate and to ensure the quality of the data, rating-based incentive mechanisms are promising. Members mutually rate the quality of their contributions and are rewarded for good contributions and truthful ratings. Until now, there has been no systematic evaluation of such rating mechanisms in the context of structured knowledge. We have developed a platform for the collaborative creation of semantic structures. To evaluate the effect of ratings and incentive mechanisms on the quality of peer-produced data, we have conducted an extensive empirical study in an online community. We show that ratings are a reliable measure of the quality of contributions by comparing user ratings with an ex post evaluation by experts. Further experimental results are that incentive mechanisms increase the quality of contributions. We conclude that ratings and incentive mechanisms are promising to foster and improve the peer production of structured knowledge.
Understanding the wikipedia phenomenon: a case for agent based modeling
Authors: Myshkin Ingawale
Venue: CIKM
Year: 2008

Wikipedia, the user led and monitored "open" encyclopedia has been an undoubted popular success. Of particular interest are the diffusion process of the innovation throughout the "contributor" community, and the question as to why unpaid, often well qualified, volunteers contribute content and time. Explanations for 'altruistic' contributor behavior based on the positivistic paradigm, and with roots in organizational psychology, while heavily researched and documented, have not been readily transferable to quantitative models of sufficient predictive value, in relation to Wikipedia's metrics. For despite the wide range of types, ages, locations and motivations of its contributors and seekers, investigators on Wikipedia have identified certain definite and often surprisingly universal trends ('laws') in its overall growth curve, organization structure, community and article formation. Models based on aggregated top-level relationships between entities on and around wikipedia suffer from assuming relationships between these entities as inputs to the wikipedia process, rather than emergent phenomena that evolve and change with the output. We argue for an Agent Based Model of Wikipedia, with the end objective of our work being a tool with diagnostic and/or prescriptive value for decision makers in organizations using or planning to use Knowledge Management Systems.
Named entity transliteration for cross-language information retrieval using compressed word format mapping algorithm
Authors: Srinivasan C. Janarthanam, Sethuramalingam Subramaniam, Udhyakumar Nallasamy
Venue: CIKM
Year: 2008

Transliteration of named entities in user queries is a vital step in any Cross-Language Information Retrieval (CLIR) system. Several methods for transliteration have been proposed till date based on the nature of the languages considered. In this paper, we present a transliteration algorithm for mapping English named entities to their proper Tamil equivalents. Our algorithm employs a grapheme-based model, in which transliteration equivalents are identified by mapping the source language names to their equivalents in a target language database, instead of generating them. The basic principle is to compress the source word into its minimal form and align it across an indexed list of target language words to arrive at the top n-equivalents based on the edit distance. We compare the performance of our approach with a statistical generation approach using Microsoft Research India (MSRI) transliteration corpus. Our approach has proved very effective in terms of accuracy and time.
MashQL: a query-by-diagram topping SPARQL
Authors: Mustafa Jarrar, Marios D. Dikaiakos
Venue: CIKM
Year: 2008

This article is motivated by the importance of building web data mashups. Building on the remarkable success of Web 2.0 mashups, and specially Yahoo Pipes, we generalize the idea of mashups and regard the Internet as a database. Each internet data source is seen as a table, and a mashup is seen as a query on these tables. We assume that web data sources are represented in RDF, and SPARQL is the query language.
Cost-effective spam detection in p2p file-sharing systems
Authors: Dongmei Jia
Venue: CIKM
Year: 2008

Spam is highly pervasive in P2P file-sharing systems and is difficult to detect automatically before actually downloading a file due to the insufficient and biased description of a file returned to a client as a query result. To alleviate this problem, we propose probing technique to collect more complete feature information of query results from the network and apply feature-based ranking for automatically detecting spam in P2P query result sets. Furthermore, we examine the tradeoff between the spam detection performance and the network cost. Different ways of probing are explored to reduce the network cost. Experimental results show that the proposed techniques successfully decrease the amount of spam by 9% in the top-200 results and by 92% in the top-20 results with reasonable cost.
Spam characterization and detection in peer-to-peer file-sharing systems
Authors: Dongmei Jia, Wai Gen Yee, Ophir Frieder
Venue: CIKM
Year: 2008

Spam is highly pervasive in P2P file-sharing systems and is difficult to detect automatically before actually downloading a file due to the insufficient and biased description of a file returned to a client as a query result. To alleviate this problem, we first characterize spam and spammers in the P2P file-sharing environment and then describe feature-based techniques for automatically detecting spam in P2P query result sets. Experimental results show that the proposed techniques successfully decrease the amount of spam by 9 % in the top-200 results and by 92 % in the top-20 results.
Vanity fair: privacy in querylog bundles
Authors: Rosie Jones, Ravi Kumar, Bo Pang, Andrew Tomkins
Venue: CIKM
Year: 2008

A recently proposed approach to address privacy concerns in storing web search querylogs is bundling logs of multiple users together. In this work we investigate privacy leaks that are possible even when querylogs from multiple users are bundled together, without any user or session identifiers. We begin by quantifying users' propensity to issue own-name vanity queries and geographically revealing queries. We show that these propensities interact badly with two forms of vulnerabilities in the bundling scheme. First, structural vulnerabilities arise due to properties of the heavy tail of the user search frequency distribution, or the distribution of locations that appear within a user's queries. These heavy tails may cause a user to appear visibly different from other users in the same bundle. Second, we demonstrate analytical vulnerabilities based on the ability to separate the queries in a bundle into threads corresponding to individual users. These vulnerabilities raise privacy issues suggesting that bundling must be handled with great care.
Privacy-preserving data publishing for horizontally partitioned databases
Authors: Pawel Jurczyk, Li Xiong
Venue: CIKM
Year: 2008

There is an increasing need for sharing data repositories containing personal information across multiple distributed, possibly untrusted, and private databases. Such data sharing is subject to constraints imposed by privacy of data subjects as well as data confidentiality of institutions or data providers. We developed a set of decentralized protocols that enable data sharing for horizontally partitioned databases given these constraints. Our approach includes a distributed anonymization protocol that allows independent data providers to build a virtual anonymized database, and a distributed querying protocol that allows clients to query the virtual database.
Towards privacy-preserving integration of distributed heterogeneous data
Authors: Pawel Jurczyk, Li Xiong
Venue: CIKM
Year: 2008

More and more applications rely heavily on large amounts of data in the distributed storages collected over time or produced by large scale scientific experiments or simulations. An important fact is that many organizations collect, store, and use various types of information about individuals. In consequence, such data sharing is subject to constraints imposed by privacy of individuals or data subjects as well as data confidentiality of institutions or data providers. Given a query spanning multiple databases, it should be executed transparently and efficiently. And most importantly, the results should not contain individually identifiable information and institutions should not reveal their databases to each other apart from the query results. In this paper, we propose a distributed anonymization protocol that allows independent data providers to build a virtual anonymized database from horizontally partitioned databases, and a secure query protocol that allows clients to query those virtual databases. We also propose a distributed data sharing and integration architecture for querying these distributed heterogeneous and possibly private databases. Our system provides efficient and scalable privacy-preserving query execution interface that integrates data seamlessly and transparently.
Scalable complex pattern search in sequential data
Authors: Leila Kaghazian, Dennis McLeod, Reza Sadri
Venue: CIKM
Year: 2008

Searching data streams has been traditionally very limited, either in the complexity of the search or in the size of the searched dataset. In this paper, we investigate the design and optimization of constructs that enable SQL to express complex patterns. In particular we propose the RSPS (recursive sequential pattern search) algorithm that inspired by the KMP (Knuth-Morris-Pratt) string matching algorithm and exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Performance gains derived from a set of experiments and a sensitivity analysis for the RSPS are also discussed. Our experimental results demonstrate impressive speedup. 1.
Estimating the number of answers with guarantees for structured queries in p2p databases
Authors: Marcel Karnstedt, Kai-Uwe Sattler, Michael Haß, Manfred Hauswirth, Brahmananda Sapkota, Roman Schmidt
Venue: CIKM
Year: 2008

Structured P2P overlays supporting standard database functionalities are a popular choice for building large-scale distributed data management systems. In such systems, estimating the number of answers for structured queries can help approximating query completeness, but is especially challenging. In this paper, we propose to use routing graphs in order to achieve this. We introduce the general approach and briefly discuss further aspects like overhead and guarantees.
Trust, authority and popularity in social information retrieval
Authors: Gabriella Kazai, Natasa Milic-Frayling
Venue: CIKM
Year: 2008

We present a social information retrieval (SIR) model comprising the social network of actors (e.g., authors, publishers, consumers), the graph representing relations in data (e.g., publications), and the links between the social and data network that reflect activities in the network such as search, authoring, annotation, etc. Building on this hybrid network, we describe relevance in terms of the trust propagated through the network and rendered onto a given item. In particular, relevance is a function of the approval votes from the associated sub-graph and the reputation of the sub-graph nodes. We explore a model that differentiates between approval from actors who are perceived authorities by the user and the approval by a wider community, representing the popular opinion.
SQL extension for exploring multiple tables
Authors: Sung Jin Kim, Junghoo John Cho
Venue: CIKM
Year: 2008

The standard SQL assumes that the users are aware of all tables and their schemas to write queries. This assumption may be valid when the users deal with a relatively small number of tables, but writing a SQL query on a large number of tables is often challenging; (1) the users do not know what tables are relevant to their query, (2) it is too cumbersome to explicitly list tens of (or even hundreds of) relevant tables in the FROM clause and (3)
Mining metastasis related genes by primary-secondary tumor comparisons from large-scale database
Authors: Sangwoo Kim, Doheon Lee
Venue: CIKM
Year: 2008

Metastasis is the most dangerous step in cancer progression and causes more than 90% of cancer death. Although many researchers have been working on biological features and characteristics of metastasis, most of its genetic level processes remain uncertain. Some studies succeeded in elucidating metastasis related genes and pathways, followed by predicting prognosis of cancer patients, but there still is a question whether the result genes or pathways contain enough information and noise features have been controlled appropriately. To address these problems, we conducted comparisons between primary tumors and secondary metastatic tumors. Noises from the differences of tissue specific characteristics between two types of tumors have been controlled by additional analyses. In this paper, we suggest a new method for identifying genes and pathways which secure metastasis dependency and are free of metastasis independent features.
An extension of PLSA for document clustering
Authors: Young-Min Kim, Jean-François Pessiot, Massih-Reza Amini, Patrick Gallinari
Venue: CIKM
Year: 2008

In this paper we propose an extension of the PLSA model in which an extra latent variable allows the model to co-cluster documents and terms simultaneously. We show on three datasets that our extended model produces statistically significant improvements with respect to two clustering measures over the original PLSA and the multinomial mixture MM models.
How evaluator domain expertise affects search result relevance judgments
Authors: Kenneth A. Kinney, Scott B. Huffman, Juting Zhai
Venue: CIKM
Year: 2008

Traditional search evaluation approaches have often relied on domain experts to evaluate results for each query. Unfortunately, the range of topics present in any representative sample of web queries makes it impractical to have expert evaluators for every topic. In this paper, we investigate the effect of using "generalist" evaluators instead of experts in the domain of queries being evaluated. Empirically, we ind that for queries drawn from domains requiring high expertise, (1) generalists tend to give shallow, inaccurate ratings as compared to experts. (2) Further experiments show that generalists disagree on the underlying meaning of these queries significantly more often than experts, and often appear to "give up'' and fall back on surface features such as keyword matching. (3) Finally, by estimating the percentage of "expertise requiring'' queries in a web query sample, we estimate the impact of using generalists, versus the ideal of having domain experts for every "expertise requiring'' query.
A densitometric approach to web page segmentation
Authors: Christian Kohlschütter, Wolfgang Nejdl
Venue: CIKM
Year: 2008

Web Page segmentation is a crucial step for many applications in Information Retrieval, such as text classification, de-duplication and full-text search. In this paper we describe a new approach to segment HTML pages, building on methods from Quantitative Linguistics and strategies borrowed from the area of Computer Vision. We utilize the notion of text-density as a measure to identify the individual text segments of a web page, reducing the problem to solving a 1D-partitioning task. The distribution of segment-level text density seems to follow a negative hypergeometric distribution, described by Frumkina's Law. Our extensive evaluation confirms the validity and quality of our approach and its applicability to the Web.
View and index selection for query-performance improvement: quality-centered algorithms and heuristics
Authors: Maxim Kormilitsin, Rada Chirkova, Yahya Fathi, Matthias F. Stallmann
Venue: CIKM
Year: 2008

Selecting and precomputing indexes and materialized views, with the goal of improving query-processing performance, is an important part of database-performance tuning. The significant complexity of the view- and index-selection problem may result in high total cost of ownership for database systems. In this paper, we develop efficient methods that deliver user-specified quality of the set of selected views and indexes when given view- and index-based plans as problem inputs. Here, quality means proximity to the globally optimum performance for the input query workload given the input query plans. Our experimental results and comparisons on synthetic and benchmark instances demonstrate the competitiveness of our approach and show that it provides a winning combination with end-to-end view- and index-selection frameworks such as those of [1, 2].
Measuring search engine quality in image queries in 10 non-English languages: an exploratory study
Authors: Fotis Lazarinis, Efthimis N. Efthimiadis
Venue: CIKM
Year: 2008

The main aim of this short paper is to measure the relevance of the retrieved images in a number of queries in different non-English languages. The reasoning behind retrieval failures is investigated and suggestions for improving these problems are discussed.
Incorporating topical support documents into a small training set in text categorization
Authors: Kyung Soon Lee
Venue: CIKM
Year: 2008

This paper explores the incorporation of topical support documents into a training set as a means of compensating for a shortage of positive training data in text categorization. To support topical representation, our method applies a simple transformation to documents, i.e., making new documents from existing positive documents by squaring a conventional term weight. The topical support documents thus created not only are expected to preserve the topic, but even improve the topical representation by emphasizing terms with higher weights. Experiments with support vector machines showed the effectiveness on RCV1 collection with a small number of positive training data. Our topical support representation achieved 52.01% and 8.83% improvements for 33 and 56 categories of RCV1 Topic in micro-averaged F1 with less than 100 and 300 positive documents in learning, respectively. Result analyses based on robustness indicate that topical support documents contribute to a steady and stable improvement.
A coarse-grain grid-based subspace clustering method for online multi-dimensional data streams
Authors: Jae Woo Lee, Won Suk Lee
Venue: CIKM
Year: 2008

This paper proposes a subspace clustering algorithm which combines grid-based clustering with frequent itemset mining. Given a d-dimensional data stream, the on-going distribution statistics of its data elements in every one-dimensional data space is monitored by a list of fine-grain grid-cells called a sibling list, so that all the one-dimensional clusters are accurately identified. By tracing a set of frequently co-occurred one-dimensional clusters, it is possible to find a coarse-grain dense rectangular space in a higher dimensional subspace. An ST-tree is introduced to continuously monitor dense rectangular spaces in all the subspaces of the d dimensions. Among the spaces, those ones whose densities are greater than or equal to a user defined minimum support threshold Smin are corresponding to final clusters.
ROAD: an efficient framework for location dependentspatial queries on road networks
Authors: Ken C. K. Lee, Wang-Chien Lee, Baihua Zheng
Venue: CIKM
Year: 2008

In this research, we develop ROAD, a system framework for processing location dependent spatial queries (LDSQs) that search for spatial objects of interest on road networks. By exploiting search space pruning, ROAD is very efficient and flexible for various LDSQs on different types of objects over large-scale networks. In ROAD, a large road network is organized as a set of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating search traversals; and 2) object abstracts for guiding object search. In this poster, we outline this framework and explain how it can support efficient location-dependent nearest neighbor search.