OpenRaiser/Intern-Atlas huggingface dataset:
Matching directories and OWL ontologies with AROMA
Authors: Jérôme David, Fabrice Guillet, Henri Briand
Venue: CIKM
Year: 2006

This paper presents a simple and adaptable matching method dealing with web directories, catalogs and OWL ontologies. By using a well-known Knowledge Discovery in Databases model, such as the association rule paradigm, this method has the originality to be both extensional and asymmetric. It works at the terminological level (by selecting concept-relevant terms contained in documents) and permits to discover equivalence and also subsumption relations holding between entities (concepts and properties). This method relies on the implication intensity measure, a probabilistic model of deviation from independence. Selection of significant rules between concepts (or properties) is lead by two criteria permitting to assess respectively the implication quality and the generativity of the rule. Finally, the proposed method is evaluated on two benchmarks. The first contains two conceptual hierarchies populated with textual documents and the second one is composed of OWL ontologies.
Constrained subspace skyline computation
Authors: Evangelos Dellis, Akrivi Vlachou, Ilya Vladimirskiy, Bernhard Seeger, Yannis Theodoridis
Venue: CIKM
Year: 2006

In this paper we introduce the problem of Constrained Subspace Skyline Queries. This class of queries can be thought of as a generalization of subspace skyline queries using range constraints. Although both constrained skyline queries and subspace skyline queries have been addressed previously, the implications of constrained subspace skyline queries has not been examined so far. Constrained skyline queries are usually more expensive than regular skylines. In case of constrained subspace skyline queries additional performance degradation is caused through the projection. In order to support constrained skylines for arbitrary subspaces, we present approaches exploiting multiple low-dimensional indexes instead of relying on a single high-dimensional index. Effective pruning strategies are applied to discard points from dominated regions. An important ingredient of our approach is the workload-adaptive strategy for determining the number of indexes and the assignment of dimensions to the indexes. Extensive performance evaluation shows the superiority of our proposed technique compared to its most related competitors.
An integer programming approach for frequent itemset hiding
Authors: Aris Gkoulalas-Divanis, Vassilios S. Verykios
Venue: CIKM
Year: 2006

The rapid growth of transactional data brought, soon enough, into attention the need of its further exploitation. In this paper, we investigate the problem of securing sensitive knowledge from being exposed in patterns extracted during association rule mining. Instead of hiding the produced rules directly, we decide to hide the sensitive frequent itemsets that may lead to the production of these rules. As a first step, we introduce the notion of distance between two databases and a measure for quantifying it. By trying to minimize the distance between the original database and its sanitized version (that can safely be released), we propose a novel, exact algorithm for association rule hiding and evaluate it on real world datasets demonstrating its effectiveness towards solving the problem. Copyright 2006 ACM.
In search of meaning for time series subsequence clustering: matching algorithms based on a new distance measure
Authors: Dina Q. Goldin, Ricardo Mardales, George Nagy
Venue: CIKM
Year: 2006

Recent papers have claimed that the result of K-means clustering for time series subsequences (STS clustering) is independent of the time series that created it. Our paper revisits this claim. In particular, we consider the following question: Given several time series sequences and a set of STS cluster centroids from one of them (generated by the K-means algorithm), is it possible to reliably determine which of the sequences produced these cluster centroids? While recent results suggest that the answer should be NO, we answer this question in the affirmative.We present cluster shape distance, an alternate distance measure for time series subsequence clusters, based on cluster shapes. Given a set of clusters, its shape is the sorted list of the pairwise Euclidean distances between their centroids. We then present two algorithms based on this distance measure, which match a set of STS cluster centroids with the time series that produced it. While the first algorithm creates DQG reuse this term more smaller "fingerprints" for the sequences, the second is more accurate. In our experiments with a dataset of 10 sequences, it produced a correct match 100% of the time.Furthermore, we offer an analysis that explains why our cluster shape distance provides a reliable way to match STS clusters to the original sequences, whereas cluster set distance fails to do so. Our work establishes for the first time a strong relation between the result of K-means STS clustering and the time series sequence that created it, despite earlier predictions that this is not possible.
Mining compressed commodity workflows from massive RFID data sets
Authors: Hector Gonzalez, Jiawei Han, Xiaolei Li
Venue: CIKM
Year: 2006

Radio Frequency Identification (RFID) technology is fast becoming a prevalent tool in tracking commodities in supply chain management applications. The movement of commodities through the supply chain forms a gigantic workflow that can be mined for the discovery of trends, flow correlations and outlier paths, that in turn can be valuable in understanding and optimizing business processes.In this paper, we propose a method to construct compressed probabilistic workflows that capture the movement trends and significant exceptions of the overall data sets, but with a size that is substantially smaller than that of the complete RFID workflow. Compression is achieved based on the following observations: (1) only a relatively small minority of items deviate from the general trend, (2)only truly non-redundant deviations, ie, those that substantially deviate from the previously recorded ones, are interesting, and (3) although RFID data is registered at the primitive level, data analysis usually takes place at a higher abstraction level. Techniques for workflow compression based on non-redundant transition and emission probabilities are derived; and an algorithm for computing approximate path probabilities is developed. Our experiments demonstrate the utility and feasibility of our design, data structure, and algorithms.
Effective and efficient similarity search in time series
Authors: Sergio Greco, Massimiliano Ruffolo, Andrea Tagarelli
Venue: CIKM
Year: 2006

We present DSA - Derivative time series Segment Approximation, a novel representation model for time series designed for effective and efficient similarity search. DSA substantially exploits derivative estimation, segmentation and dimensionality reduction to meet at least the requirements of high sensitivity to main features (trends) of time series and robustness to outliers. Experiments show that DSA is drastically faster and still as good or better than the prominent state-of-the-art similarity methods.
Cache-oblivious nested-loop joins
Authors: Bingsheng He, Qiong Luo
Venue: CIKM
Year: 2006

We propose to adapt the newly emerged cache-oblivious model to relational query processing. Our goal is to automatically achieve an overall performance comparable to that of fine-tuned algorithms on a multi-level memory hierarchy. This automaticity is because cache-oblivious algorithms assume no knowledge about any specific parameter values, such as the capacity and block size of each level of the hierarchy. As a first step, we propose recursive partitioning to implement cache-oblivious nested-loop joins (NLJs) without indexes, and recursive clustering and buffering to implement cache-oblivious NLJs with indexes. Our theoretical results and empirical evaluation on three different architectures show that our cache-oblivious NLJs match the performance of their manually optimized, cache-conscious counterparts.
Resource-aware kernel density estimators over streaming data
Authors: Christoph Heinz, Bernhard Seeger
Venue: CIKM
Year: 2006

A fundamental building block of many data mining and analysis approaches is density estimation as it provides a comprehensive statistical model of a data distribution. For that reason, its application to transient data streams is highly desirable. A convenient, nonparametric method for density estimation utilizes kernels. However, its computational complexity collides with the rigid processing requirements of data streams. In this work, we present a new approach to this problem that combines linear processing cost with a constant amount of allocated memory. Our approach also supports a dynamic memory adaptation to changing system resources.
A structure-oriented relevance feedback method for XML retrieval
Authors: Lobna Hlaoua, Karen Sauvagnat, Mohand Boughanem
Venue: CIKM
Year: 2006

Relevance Feedback (RF) is a technique allowing to enrich an initial query according to the user feedback. The goal is to express more precisily the user's needs. Some open issues appear when considering semi-structured documents like XML documents. Most of the RF approaches proposed in XML retrieval are simple adaptations of traditional RF to the new granularity of information. They enrich queries by adding terms extracted from relevant elements instead of terms extracted from whole documents. In this paper we show how structural constraints can also be used in RF. We propose a new approach that is able to extend the initial query by adding one or more generative structures. This approach is applied to unstructured queries. Experiments are carried out on INEX collection and results show the interest of our method.
Task-based process know-how reuse and proactive information delivery in TaskNavigator
Authors: Harald Holz, Oleg Rostanin, Andreas Dengel, Takeshi Suzuki, Kaoru Maeda, Katsumi Kanasaki
Venue: CIKM
Year: 2006

Knowledge management approaches for weakly-structured, adhoc knowledge work processes need to be lightweight, i.e., they cannot rely on high upfront modeling efforts. This paper presents TaskNavigator, a novel prototype to support weakly-structured processes by integrating a standard task list application with a state-of-the-art document classification system. The resulting system allows for a task-oriented view on office workers' personal knowledge spaces in order to realize a proactive and contextsensitive information support during daily, knowledge-intensive tasks. Moreover, TaskNavigator supports process know-how reuse by proactively suggesting similar tasks or relevant process models, based on textual similarities. Finally, we report on a feasibility test and a case study that have been conducted in order to evaluate the system in the context of daily research task management and software requirements analysis.
Processing relaxed skylines in PDMS using distributed data summaries
Authors: Katja Hose, Christian Lemke, Kai-Uwe Sattler
Venue: CIKM
Year: 2006

Peer Data Management Systems (PDMS) are a natural extension of heterogeneous database systems. One of the main tasks in such systems is efficient query processing. Insisting on complete answers, however, leads to asking almost every peer in the network. Relaxing these completeness requirements by applying approximate query answering techniques can significantly reduce costs. Since most users are not interested in the exact answers to their queries, rank-aware query operators like top-k or skyline play an important role in query processing. In this paper, we present the novel concept of relaxed skylines that combines the advantages of both rank-aware query operators and approximate query processing techniques. Furthermore, we propose a strategy for processing relaxed skylines in distributed environments that allows for giving guarantees for the completeness of the result using distributed data summaries as routing indexes.
Continuous keyword search on multiple text streams
Authors: Vagelis Hristidis, Oscar Valdivia, Michail Vlachos, Philip S. Yu
Venue: CIKM
Year: 2006

In this paper we address the issue of continuous keyword queries on multiple textual streams. This line of work represents a significant departure from previous keyword search models that assumed a static database. In our model the user poses a query comprised by a collection of keywords, which is subsequently applied on multiple text streams (these can be RSS news feeds, TV closed captions, emails, etc). A result to a query is a combination of streams sufficiently correlated to each other that collectively contain all query keywords within a specified time span.
Integration of cluster ensemble and EM based text mining for microarray gene cluster identification and annotation
Authors: Xiaohua Hu, Xiaodan Zhang, Xiaohua Zhou
Venue: CIKM
Year: 2006

In this paper, we design and develop a unified system GE-Miner (Gene Expression Miner) to integrate cluster ensemble, text clustering and multi document summarization and provide an environment for comprehensive gene expression data analysis. We present a novel cluster ensemble approach to generate high quality gene cluster. In our text summarization module, given a gene cluster, our Expectation Maximization (EM) based algorithm can automatically identify subtopics and extract most probable terms for each topic. Then, the extracted top k topical terms from each subtopic are combined to form the biological explanation of each gene cluster. Experimental results demonstrate that our system can obtain high quality clusters and provide informative key terms for the gene clusters.
On progressive sequential pattern mining
Authors: Jen-Wei Huang, Chi-Yao Tseng, Jian Chih Ou, Ming-Syan Chen
Venue: CIKM
Year: 2006

When sequential patterns are generated, the newly arriving patterns may not be identified as frequent sequential patterns due to the existence of old data and sequences. In practice, users are usually more interested in the recent data than the old ones. To capture the dynamic nature of data addition and deletion, we propose a general model of sequential pattern mining with a progressive database. In addition, we present a progressive concept to progressively discover sequential patterns in recent time period of interest.
Efficient range-constrained similarity search on wavelet synopses over multiple streams
Authors: Hao-Ping Hung, Ming-Syan Chen
Venue: CIKM
Year: 2006

Due to the resource limitation in the data stream environment, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a Data Stream Management System (DSMS). In this paper, motivated by the fact that a user may be interested in an arbitrary range of the data streams, we investigate two important types of range-constrained queries in time series streaming environments: the distance queries (which aim at obtaining the Euclidean distance between two streams) and the kNN queries (which aim at discovering k nearest neighbors to a reference stream). To achieve high efficiency in processing these two types of queries, we propose procedure RED (standing for Range-constrained Euclidean Distance) and algorithm EKS (standing for Enhanced KNN Search). Compared to the existing methods in the prior research, the advantageous features of our approaches are in two folds. First, our approaches are capable of processing the queries directly from the wavelet synopses retained in the main memory without using IDWT to reconstruct the data cells. This feature allows us to save the complexity in both memory and time. Moreover, our approaches enable the users to query the DSMS within their range of interest. Unlike the conventional methods which only support the full-range query processing, this feature will enhance the flexibility at the client side. We evaluate procedure RED and algorithm EKS on live and synthetic datasets empirically and show that the proposed approaches are efficient in similarity search and kNN discovery within arbitrary ranges in the time series streaming environments.
Adaptive non-linear clustering in data streams
Authors: Ankur Jain, Zhihua Zhang, Edward Y. Chang
Venue: CIKM
Year: 2006

Data stream clustering has emerged as a challenging and interesting problem over the past few years. Due to the evolving nature, and one-pass restriction imposed by the data stream model, traditional clustering algorithms are inapplicable for stream clustering. This problem becomes even more challenging when the data is high-dimensional and the clusters are not linearly separable in the input space. In this paper, we propose a nonlinear stream clustering algorithm that adapts to the stream's evolutionary changes. Using the kernel methods for dealing with the non-linearity of data separation, we propose a novel 2-tier stream clustering architecture. Tier-1 captures the temporal locality in the stream, by partitioning it into segments, using a kernel-based novelty detection approach. Tier-2 exploits this segment structure to continuously project the streaming data nonlinearly onto a low-dimensional space (LDS), before assigning them to a cluster. We demonstrate the effectiveness of our approach through extensive experimental evaluation on various real-world datasets.
An efficient one-phase holistic twig join algorithm for XML data
Authors: Zhewei Jiang, Cheng Luo, Wen-Chi Hou
Venue: CIKM
Year: 2006

In view of the inefficiency of the traditional two-phase Twig-Stack algorithm, we propose a single-phase holistic twig pattern matching method based on the TwigStack algorithm by applying a novel stack structure.
The real-time nature and value of homeland security information
Authors: Joseph Kielman
Venue: CIKM
Year: 2006

Ensuring the security of our homeland depends in large measure on two quite distinct factors: having the knowledge necessary to prevent, predict, prepare for, or respond, if necessary, to any manner of terrorist attack or a natural or manmade disaster and collaborating or sharing knowledge with a broad range of international, federal, state, local, and tribal agencies, as well as other private or public organizations. The essential problem with adequately addressing these factors, despite the many advancements made in the past decade, is twofold. First, it is not so much the mass but rather the diffuse nature and complexity of the data, information, and knowledge required for understanding terrorism and accounting for the manifold consequences of disasters that make possession of the right knowledge difficult. And, second, that diffuseness and complexity is magnified by the extreme diversity and wide distribution of the many potential homeland security collaborators. Retrospective analysis, and even knowledge discovery, is less useful under these conditions than prospective, real-time synthesis of information for multiple users. Also, privacy is as important as, if not more important than, security. This suggests that database designs and techniques for information retrieval, and knowledge management must take advantage of such technologies as semantic nets, visualization, and discrete mathematics to build knowledge systems capable for homeland security applications.
CP/CV: concept similarity mining without frequency information from domain describing taxonomies
Authors: Jong Wook Kim, K. Selçuk Candan
Venue: CIKM
Year: 2006

Domain specific ontologies are heavily used in many applications. For instance, these form the bases on which similarity/dissimilarity between keywords are extracted for various knowledge discovery and retrieval tasks. Existing similarity computation schemes can be categorized as (a) structure- or (b) information-based approaches. Structure based approaches compute dissimilarity between keywords using a (weighted) count of edges between two keywords. Information-base approaches, on the other hand, leverage available corpora to extract additional information, such as keyword frequency, to achieve better performance in similarity computation than structure-based approaches. Unfortunately, in many application domains (such as applications that rely on unique-keys in a relational database), frequency information required by information-based approaches does not exist. In this paper, we note that there is a third way of computing similarity: if each node in a given hierarchy can be represented as a vector of related concepts, these vectors could be compared to compute similarities. This requires mapping concept-nodes in a given hierarchy onto a concept space. In this paper, we propose a concept propagation (CP) scheme, which relies on the semantical relationships between concepts implied by the structure of the hierarchy to annotate each concept-node with a concept-vector (CV). We refer to this approach as CP/CV. Comparison of keyword similarity results shows that CP/CV provides significantly better (upto 33%) results than existing structure-based schemes. Also, even if CP/CV does not assume the availability of an appropriate corpus to extract keyword frequency information, our approach matches (and slightly improves on) the performance of information-based approaches.
Matching and evaluation of disjunctive predicates for data stream sharing
Authors: Richard Kuntschke, Alfons Kemper
Venue: CIKM
Year: 2006

New optimization techniques, e.g., in data stream management systems (DSMSs), make the treatment of disjunctive predicates a necessity. In this paper, we introduce and compare methods for matching and evaluating disjunctive predicates.
The visual funding navigator: analysis of the NSF funding information
Authors: Shixia Liu, Nan Cao, Hao Lv, Hui Su
Venue: CIKM
Year: 2006

This paper presents an interactive visualization toolkit for navigating and analyzing the National Science Foundation (NSF) funding information. Our design builds upon an improved 2.5D treemap layout and the stacked graph to contribute customized techniques for visually navigating and interacting with the hierarchical data of NSF programs and proposals. Furthermore, an incremental layout method is adopted to handle information on a large scale. The improved treemap visualization will help to visually analyze the static funding related data and the stacked graph is utilized to analyze the time-series data. Through these visual analysis techniques, research trends of NSF, popular NSF programs are quickly identified.
Measuring the meaning in time series clustering of text search queries
Authors: Bing Liu, Rosie Jones, Kristina Lisa Klinkner
Venue: CIKM
Year: 2006

We use a combination of proven methods from time series analysis and machine learning to explore the relationship between temporal and semantic similarity in web query logs; we discover that the combination of correlation and cycles is a good, but not perfect, sign of semantic relationship.