OpenRaiser/Intern-Atlas huggingface dataset:
Focused crawling for both topical relevance and quality of medical information
Authors: Thanh Tin Tang, David Hawking, Nick Craswell, Kathleen Griffiths
Venue: CIKM
Year: 2005

Subject-specific search facilities on health sites are usually built using manual inclusion and exclusion rules. These can be expensive to maintain and often provide incomplete coverage of Web resources. On the other hand, health information obtained through whole-of-Web search may not be scientifically based and can be potentially harmful.To address problems of cost, coverage and quality, we built a focused crawler for the mental health topic of depression, which was able to selectively fetch higher quality relevant information. We found that the relevance of unfetched pages can be predicted based on link anchor context, but the quality cannot. We therefore estimated quality of the entire linking page, using a learned IR-style query of weighted single words and word pairs, and used this to predict the quality of its links. The overall crawler priority was determined by the product of link relevance and source quality.We evaluated our crawler against baseline crawls using both relevance judgments and objective site quality scores obtained using an evidence-based rating scale. Both a relevance focused crawler and the quality focused crawler retrieved twice as many relevant pages as a breadth-first control. The quality focused crawler was quite effective in reducing the amount of low quality material fetched while crawling more high quality content, relative to the relevance focused crawler.Analysis suggests that quality of content might be improved by post-filtering a very big breadth-first crawl, at the cost of substantially increased network traffic.
A new framework to combine descriptors for content-based image retrieval
Authors: Ricardo da Silva Torres, Alexandre X. Falcão, Baoping Zhang, Weiguo Fan, Edward A. Fox, Marcos André Gonçalves, Pável Calado
Venue: CIKM
Year: 2005

In this paper, we propose a novel framework using Genetic Programming to combine image database descriptors for content-based image retrieval (CBIR). Our framework is validated through several experiments involving two image databases and specific domains, where the images are retrieved based on the shape of their objects.
Structure-based query-specific document summarization
Authors: Ramakrishna Varadarajan, Vagelis Hristidis
Venue: CIKM
Year: 2005

Summarization of text documents is increasingly important with the amount of data available on the Internet. The large majority of current approaches view documents as linear sequences of words and create query-independent summaries. However, ignoring the structure of the document degrades the quality of summaries. Furthermore, the popularity of web search engines requires query-specific summaries. We present a method to create query-specific summaries by adding structure to documents by extracting associations between their fragments.
Rotation invariant indexing of shapes and line drawings
Authors: Michail Vlachos, Zografoula Vagena, Philip S. Yu, Vassilis Athitsos
Venue: CIKM
Year: 2005

We present data representations, distance measures and organizational structures for fast and efficient retrieval of similar shapes in image databases. Using the Hough Transform we extract shape signatures that correspond to important features of an image. The new shape descriptor is robust against line discontinuities and takes into consideration not only the shape boundaries, but also the content inside the object perimeter. The object signatures are eventually projected into a space that renders them invariant to translation, scaling and rotation. In order to provide support for real-time query-by-content, we also introduce an index structure that hierarchically organizes compressed versions of the extracted object signatures. In this manner we can achieve a significant performance boost for multimedia retrieval. Our experiments suggest that by exploiting the proposed framework, similarity search in a database of 100,000 images would require under 1 sec, using an off-the-shelf personal computer.
Using RankBoost to compare retrieval systems
Authors: Huyen-Trang Vu, Patrick Gallinari
Venue: CIKM
Year: 2005

This paper presents a new pooling method for constructing the assessment sets used in the evaluation of retrieval systems. Our proposal is based on RankBoost, a machine learning voting algorithm. It leads to smaller pools than classical pooling and thus reduces the manual assessment workload for building test collections. Experimental results obtained on an XML document collection demonstrate the effectiveness of the approach according to different evaluation criteria.
The earth mover's distance as a semantic measure for document similarity
Authors: Xiaojun Wan, Yuxin Peng
Venue: CIKM
Year: 2005

Different words are usually assumed to be semantically independent in most existing similarity measures, which is not often true in practice. The semantic relatedness between words cannot be conveniently employed in the existing measures. We propose a novel similarity measure based on the earth mover's distance (EMD). In the proposed measure, the semantic distances between words are computed based on the electronic lexical database-WordNet and then the EMD is employed to calculate the document similarity with a many-to-many matching between words. Experiments and results demonstrate the effectiveness of the proposed similarity measure.
A framework for mining topological patterns in spatio-temporal databases
Authors: Junmei Wang, Wynne Hsu, Mong-Li Lee
Venue: CIKM
Year: 2005

Mining topological patterns in spatial databases has received a lot of attention. However, existing work typically ignores the temporal aspect and suffers from certain efficiency problems. They are not scalable for mining topological patterns in spatio-temporal databases. In this paper, we study the problem for mining topological patterns by incorporating the temporal aspect in the mining process. We introduce a summary-structure that records the instances' count information of a feature in a region within a time window. Using this structure, we design an algorithm, TopologyMiner, to find interesting topological patterns without the need to generate candidates. Experimental results show that TopologyMiner is effective and scalable in finding topological patterns and outperforms Apriori-like algorithm by a few orders of magnitudes.
A latent semantic classification model
Authors: Ming-Wen Wang, Jian-Yun Nie, Xue-Qiang Zeng
Venue: CIKM
Year: 2005

Latent Semantic Indexing (LSI) has been successfully applied to information retrieval and text classification. However, when LSI is used in classification, some important features for small classes may be ignored because of their small feature values. To solve this problem, we propose the latent semantic classification (LSC) model which extends the LSI model in the following way: the classification information of the training documents is introduced into the latent semantic structure via a second set of latent variables, so that both indexing and classification information can be taken into account during the classification process. Our experiments on Reuters show that our new model performs better than the existing classification methods such as kNN and SVM.
Domain-specific keyphrase extraction
Authors: Yi-fang Brook Wu, Quanzhi Li, Razvan Stefan Bot, Xin Chen
Venue: CIKM
Year: 2005

Document keyphrases provide semantic metadata characterizing documents and producing an overview of the content of a document. They can be used in many text-mining and knowledge management related applications. This paper describes a Keyphrase Identification Program (KIP), which extracts document keyphrases by using prior positive samples of human identified domain keyphrases to assign weights to the candidate keyphrases. The logic of our algorithm is: the more keywords a candidate keyphrase contains and the more significant these keywords are, the more likely this candidate phrase is a keyphrase. To obtain prior positive inputs, KIP first populates its glossary database using manually identified keyphrases and keywords. It then checks the composition of all noun phrases of a document, looks up the database and calculates scores for all these noun phrases. The ones having higher scores will be extracted as keyphrases.
A formal characterization of PIVOT/UNPIVOT
Authors: Catharine M. Wyss, Edward L. Robertson
Venue: CIKM
Year: 2005

PIVOT is an important relational operation that allows data in rows to be exchanged for columns. Although most current relational database management systems support PIVOT-type operations, to date a purely formal, algebraic characterization of PIVOT has been lacking. In this paper, we present a characterization in terms of extended relational algebra operators τ (transpose), Π (drop projection), and μ (unique optimal tuple merge). This enables us to (1) draw parallels with PIVOT and existing operators employed in Dynamic Data Mapping Systems (DDMS), (2) formally characterize invertible PIVOT instances, and (3) provide complexity results for PIVOT-type operations. These contributions are an important part of ongoing work on formal models for relational OLAP.
ERkNN: efficient reverse k-nearest neighbors retrieval with local kNN-distance estimation
Authors: Chenyi Xia, Wynne Hsu, Mong-Li Lee
Venue: CIKM
Year: 2005

The Reverse k-Nearest Neighbors (RkNN) queries are important in profile-based marketing, information retrieval, decision support and data mining systems. However, they are very expensive and existing algorithms are not scalable to queries in high dimensional spaces or of large values of k. This paper describes an efficient estimation-based RkNN search algorithm (ERkNN) which answers RkNN queries based on local kNN-distance estimation methods. The proposed approach utilizes estimation-based filtering strategy to lower the computation cost of RkNN queries. The results of extensive experiments on both synthetic and real life datasets demonstrate that ERkNN algorithm retrieves RkNN efficiently and is scalable with respect to data dimensionality, k, and data size.
Slicing*-tree based web page transformation for small displays
Authors: Xiangye Xiao, Qiong Luo, Dan Hong, Hongbo Fu
Venue: CIKM
Year: 2005

We propose a new Web page transformation method for browsing on mobile devices with small displays. In our approach, an original web page that does not fit into the screen is transformed into a set of pages, each of which fits into the screen. This transformation is done through slicing the original page. The resulting set of transformed pages form a multi-level tree structure, called a slicing*-tree, in which an internal node consists of a thumbnail image with hyperlinks and a leaf node is a block from the original web page. Our slicing*-tree based Web page transformation eases Web browsing on small displays by providing screen-fitting visual context and reducing page scrolling effort.
Cooperative caching for k-NN search in ad hoc networks
Authors: Bo Yang, Ali R. Hurson
Venue: CIKM
Year: 2005

Mobile ad hoc networks have multiple limitations in performing similarity-based nearest neighbor search - dynamic topology, frequent disconnections, limited power, and restricted bandwidth. Cooperative caching is an effective technique to reduce network traffic and increase accessibility. In this paper, we propose to solve the k-nearest-neighbor search problem in ad hoc networks using a semantic-based caching scheme which reflects the content distribution in the network. The proposed scheme describes the semantic similarity among data objects using constraints, and employs cooperative caching to estimate the content distribution in the network. The query resolution based on the cooperative caching scheme is non-flooding and hierarchy-free.
An RSA-based time-bound hierarchical key assignment scheme for electronic article subscription
Authors: Jyh-haw Yeh
Venue: CIKM
Year: 2005

The time-bound hierarchical key assignment problem is to assign time sensitive keys to security classes in a partially ordered hierarchy so that legal data accesses among classes can be enforced. Two time-bound hierarchical key assignment schemes have been proposed in the literature, but both of them were proved insecure against collusive attacks. In this paper, we will propose an RSA-based time-bound hierarchical key assignment scheme and describe its possible application. The security analysis shows that the new scheme is safe against the collusive attacks.
Towards estimating the number of distinct value combinations for a set of attributes
Authors: Xiaohui Yu, Calisto Zuzarte, Kenneth C. Sevcik
Venue: CIKM
Year: 2005

Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.
Intelligent GP fusion from multiple sources for text classification
Authors: Baoping Zhang, Yuxin Chen, Weiguo Fan, Edward A. Fox, Marcos André Gonçalves, Marco Cristo, Pável Calado
Venue: CIKM
Year: 2005

This paper shows how citation-based information and structural content (e.g., title, abstract) can be combined to improve classification of text documents into predefined categories. We evaluate different measures of similarity -- five derived from the citation information of the collection, and three derived from the structural content -- and determine how they can be fused to improve classification effectiveness. To discover the best fusion framework, we apply Genetic Programming (GP) techniques. Our experiments with the ACM Computing Classification Scheme, using documents from the ACM Digital Library, indicate that GP can discover similarity functions superior to those based solely on a single type of evidence. Effectiveness of the similarity functions discovered through simple majority voting is better than that of content-based as well as combination-based Support Vector Machine classifiers. Experiments also were conducted to compare the performance between GP techniques and other fusion techniques such as Genetic Algorithms (GA) and linear fusion. Empirical results show that GP was able to discover better similarity functions than GA or other fusion techniques.
Discovering strong skyline points in high dimensional spaces
Authors: Zhenjie Zhang, Xinyu Guo, Hua Lu, Anthony K. H. Tung, Nan Wang
Venue: CIKM
Year: 2005

Current interests in skyline computation arise due to their relation to preference queries. Since it is guaraneed that a skyline point will not lose out in all dimensions when compared to any other point in the data set, this means that for each skyline point, there exists a set of weight assignments to the dimensions such that the point will become the top user preference.We believe that the usefulness of skyline points is not limited to such application and can be extended to data analysis and knowledge discovery as well. However, since the skyline of high dimensional datasets (which are common in data analysis applications) can contain too many points, various means must be developed to filter off the less interesting skyline points in high dimensions. In this paper, we will propose algorithms to find a set of interesting skyline points called strong skyline points. Extensive experiments show that our proposal is both effective and efficient.
Mining conserved XML query paths for dynamic-conscious caching
Authors: Qiankun Zhao, Sourav S. Bhowmick, Le Gruenwald
Venue: CIKM
Year: 2005

Existing XML query pattern-based caching strategies focus on extracting the set of frequently issued query pattern trees based on the number of occurrences of the query pattern trees in the history. Each occurrence of the same query pattern tree is considered equally important for the caching strategy. However, the same query pattern tree may occur at different timepoints in the history of XML queries. This temporal feature can be used to improve the caching strategy. In this paper, we propose a novel type of query pattern called conserved query paths for efficient caching by integrating the support and temporal features together. Conserved query paths are paths in query pattern trees that never change or do not change significantly most of the time (if not always) in terms of their support values during a specific time period. We proposed an algorithm to extract those conserved query paths. By ranking those conserved query paths, a dynamic-conscious caching (DCC) strategy is proposed for efficient XML query processing. Experiments show that the DCC caching strategy outperforms the existing XML query pattern tree-based caching strategies.
WAM-Miner: in the search of web access motifs from historical web log data
Authors: Qiankun Zhao, Sourav S. Bhowmick, Le Gruenwald
Venue: CIKM
Year: 2005

Existing web usage mining techniques focus only on discovering knowledge based on the statistical measures obtained from the static characteristics of web usage data. They do not consider the dynamic nature of web usage data. In this paper, we focus on discovering novel knowledge by analyzing the change patterns of historical web access sequence data. We present an algorithm called W<small>AM</small>-M<small>INER</small> to discover Web Access Motifs (WAMs). WAMs are web access patterns that never change or do not change significantly most of the time (if not always) in terms of their support values during a specific time period. WAMs are useful for many applications, such as intelligent web advertisement, web site restructuring, business intelligence, and intelligent web caching.
Opportunity map: a visualization framework for fast identification of actionable knowledge
Authors: Kaidi Zhao, Bing Liu, Thomas M. Tirpak, Weimin Xiao
Venue: CIKM
Year: 2005

Data mining techniques frequently find a large number of patterns or rules, which make it very difficult for a human analyst to interpret the results and to find the truly interesting and actionable rules. Due to the subjective nature of "interestingness", human involvement in the analysis process is crucial. In this paper, we propose a novel visual data mining framework for the purpose of identifying actionable knowledge quickly and easily from discovered rules and data. This framework is called the Opportunity Map. It is inspired by some interesting ideas from Quality Engineering, in particular Quality Function Deployment (QFD) and the House of Quality. It associates summarized data or discovered rules with the application objective using an interactive matrix, which enables the user to quickly identify where the opportunities are. The proposed system can be used to visually analyze discovered rules, and other statistical properties of the data. The user can also interactively group actionable attributes and values, and see how they affect the targets of interest. Combined with drill-down and comparative analysis, the user can analyze rules and data at different levels of detail. The proposed visualization framework thus represents a systematic and yet flexible method of rule analysis. Applications of the system to large-scale data sets from our industrial partner have yielded promising results.
Hybrid index structures for location-based web search
Authors: Yinghua Zhou, Xing Xie, Chuang Wang, Yuchang Gong, Wei-Ying Ma
Venue: CIKM
Year: 2005

There is more and more commercial and research interest in location-based web search, i.e. finding web content whose topic is related to a particular place or region. In this type of search, location information should be indexed as well as text information. However, the index of conventional text search engine is set-oriented, while location information is two-dimensional and in Euclidean space. This brings new research problems on how to efficiently represent the location attributes of web pages and how to combine two types of indexes. In this paper, we propose to use a hybrid index structure, which integrates inverted files and R*-trees, to handle both textual and location aware queries. Three different combining schemes are studied: (1) inverted file and R*-tree double index, (2) first inverted file then R*-tree, (3) first R*-tree then inverted file. To validate the performance of proposed index structures, we design and implement a complete location-based web search engine which mainly consists of four parts: (1) an extractor which detects geographical scopes of web pages and represents geographical scopes as multiple MBRs based on geographical coordinates; (2) an indexer which builds hybrid index structures to integrate text and location information; (3) a ranker which ranks results by geographical relevance as well as non-geographical relevance; (4) an interface which is friendly for users to input location-based search queries and to obtain geographical and textual relevant results. Experiments on large real-world web dataset show that both the second and the third structures are superior in query time and the second is slightly better than the third. Additionally, indexes based on R*-trees are proven to be more efficient than indexes based on grid structures.
Approximate reverse k-nearest neighbor queries in general metric spaces
Authors: Elke Achtert, Christian Böhm, Peer Kröger, Peter Kunath, Alexey Pryakhin, Matthias Renz
Venue: CIKM
Year: 2006

In this paper, we propose an approach for efficient approximative RkNN search in arbitrary metric spaces where the value of k is specified at query time. Our method uses an approximation of the nearest-neighbor-distances in order to prune the search space. In several experiments, our solution scales significantly better than existing non-approximative approaches while producing an approximation of the true query result with a high recall.