OpenRaiser/Intern-Atlas huggingface dataset:
Caching Constrained Mobile Data
Authors: Subhasish Mazumdar, Mateusz Pietrzyk, Panos K. Chrysanthis
Venue: CIKM
Year: 2001

As mobile devices get ubiquitous and grow in computational power, their management of interdependent data also becomes increasingly important. The mobile environment exhibits all the characteristics of a distributed database plus the feature of whimsical connectivity. Consequently, transactions respecting data consistency can suffer unbounded and unpredictable delays at both mobile and stationary nodes. The currently popular multi-tier model, in which mobile devices are in one end and always-connected stationary servers in the other, has certain practical advantages. However, it assumes that all integrity constraints are evaluated at the servers and hence relies on the semantics of operations for any autonomy enhancement of the mobile devices. In this paper, we examine the idea of constraint localization in cases where two mobile nodes each own data that share a constraint. It relies on reformulation of a constraint into more flexible local constraints that give more autonomy to the mobile nodes. The scheme also involves dynamic changes of these local constraints through negotiation, which we call re-localization. To overcome the problem of simultaneous requests for such re-localization, we give algorithms along with experimental results indicating their effectiveness.
Irregularity in Multi-Dimensional Space-Filling Curves with Applications in Multimedia Databases
Authors: Mohamed F. Mokbel, Walid G. Aref
Venue: CIKM
Year: 2001

A space-filling curve is a way of mapping the multi-dimensional space into the one-dimensional space. It acts like a thread that passes through every cell element (or pixel) in the N-dimensional space so that every cell is visited at least once. Thus, a space-filling curve imposes a linear order of the cells in the N-dimensional space. There are numerous kinds of space-filling curves. The difference between such curves is in their way of mapping to the one-dimensional space. Selecting the appropriate curve for any application requires a brief knowledge of the mapping scheme provided by each space-filling curve. Irregularity is proposed as a quantitative measure of the quality of the mapping of the space-filling curve. Closed formulas are developed to compute the irregularity for any general dimension D with N points in each dimension for different space-filling curves.A comparative study of different space-filling curves with respect to irregularity is conducted and results are presented and discussed. The applicability of this research is the area of multimedia databases is illustrated with a discussion of the problems that arise.
Relevance Score Normalization for Metasearch
Authors: Mark H. Montague, Javed A. Aslam
Venue: CIKM
Year: 2001

Given the ranked lists of documents returned by multiple search engines in response to a given query, the problem of metasearch is to combine these lists in a way which optimizes the performance of the combination. This problem can be naturally decomposed into three subproblems: (1) normalizing the relevance scores given by the input systems, (2) estimating relevance scores for unretrieved documents, and (3) combining the newly-acquired scores for each document into one, improved score.Research on the problem of metasearch has historically concentrated on algorithms for combining (normalized) scores. In this paper, we show that the techniques used for normalizing relevance scores and estimating the relevance scores of unretrieved documents can have a significant effect on the overall performance of metasearch. We propose two new normalization/estimation techniques and demonstrate empirically that the performance of well known metasearch algorithms can be significantly improved through their use.
XML, the WEB and Database Functionality?
Authors: Erich J. Neuhold
Venue: CIKM
Year: 2001

With the advance of XML, DTD's, XML-Schema, X-Path, X-Link, XML-Query, XML-Protocol, RDF, Semantic WEB and other information description tools and mechanisms the WEB develops more and more into a huge structured information and data network that becomes computer processable via "semi"-automatic "intelligent" means.However, most of these multimedia information resources are kept in hierarchical file-type systems or relatively unstructured relational systems with none or very little of what is commonly known as "database functionality" for the various information types represented.
Learning Probabilistic Datalog Rules for Information Classification and Transformation
Authors: Henrik Nottelmann, Norbert Fuhr
Venue: CIKM
Year: 2001

Probabilistic Datalog is a combination of classical Datalog (i.e., function-free Horn clause predicate logic) with probability theory. Therefore, probabilistic weights may be attached to both facts and rules. But it is often impossible to assign exact rule weights or even to construct the rules themselves. Instead of specifying them manually, learning algorithms can be used to learn both rules and weights. In practice, these algorithms are very slow because they need a large example set and have to test a high number of rules. We apply a number of extensions to these algorithms in order to improve efficiency. Several applications demonstrate the power of learning probabilistic Datalog rules, showing that learning rules is suitable for low dimensional problems (e.g., schema mapping) but inappropriate for higher dimensions like e.g. in text classification.
FOCI: Flexible Organizer for Competitive Intelligence
Authors: Hwee-Leng Ong, Ah-Hwee Tan, Jamie Ng, Hong Pan, Qiu-Xiang Li
Venue: CIKM
Year: 2001

This paper describes how an integrated web-based application, code-named FOCI (Flexible Organizer for Competitive Intelligence), can help the knowledge worker in the gathering, organizing, tracking, and dissemination of competitive intelligence or knowledge bases on the web. It shows how text mining techniques including a novel user-configurable clustering, trend analysis and visualization techniques can be used synergistically to address the problem of managing information gathered from the web. FOCI allows a user to define and personalize the organization of the information clusters according to their needs and preferences into portfolios. Predefined sections for organizing information in specific domains is also supported. The personalized portfolios created can be saved and subsequently tracked and shared with other users. In addition, FOCI is designed to handle multilingual documents.
The Enosys Markets Data Integration Platform: Lessons from the Trenches
Authors: Yannis Papakonstantinou, Vasilis Vassalos
Venue: CIKM
Year: 2001

Enosys Markets offers a state-of-the-art data integration software platform to support the development of the next generation of eBusiness applications that deliver value by providing new levels of function for customer relationship management, e-commerce, supply chain management, and decision support. These applications require that data be integrated from information sources that exist both within and across organizational boundaries. The Enosys Markets data integration architecture and product family provides a complete end-to-end XML-based solution for integrating and querying distributed information sources. It incorporates advanced research into XML and database technology. We present the product architecture and components, discuss the key technical challenges, and outline the technical concepts and innovations employed in the Enosys platform.
Prefix-Querying: An Approach for Effective Subsequence Matching Under Time Warping in Sequence Databases
Authors: Sanghyun Park, Sang-Wook Kim, June-Suh Cho, Sriram Padmanabhan
Venue: CIKM
Year: 2001

This paper discusses an index-based subsequence matching that supports time warping in large sequence databases. Time warping enables finding sequences with similar patterns even when they are of different lengths. In our earlier work, we suggested an efficient method for whole matching under time warping. This method constructs a multi-dimensional index on a set of feature vectors, which are invariant to time warping, from data sequences. For filtering at feature space, it also applies a lower-bound function, which consistently underestimates the time warping distance as well as satisfies the triangular inequality.In this paper, we incorporate the prefix-querying approach based on sliding windows into the earlier approach. For indexing, we extract a feature vector from every subsequence inside a sliding window and construct a multi-dimensional index using a feature vector as indexing attributes. For query processing, we perform a series of index searches using the feature vectors of qualifying query prefixes. Our approach provides effective and scalable subsequence matching even with a large volume of a database. We also prove that our approach does not incur false dismissal. To verify the superiority of our method, we perform extensive experiments. The results reveal that our method achieves significant speedup with real-world S&P 500 stock data and with very large synthetic data.
Multi-Dimensional Sequential Pattern Mining
Authors: Helen Pinto, Jiawei Han, Jian Pei, Ke Wang, Qiming Chen, Umeshwar Dayal
Venue: CIKM
Year: 2001

Sequential pattern mining, which finds the set of frequent subsequences in sequence databases, is an important data-mining task and has broad applications. Usually, sequence patterns are associated with different circumstances, and such circumstances form a multiple dimensional space. For example, customer purchase sequences are associated with region, time, customer group, and others. It is interesting and useful to mine sequential patterns associated with multi-dimensional information.In this paper, we propose the theme of multi-dimensional sequential pattern mining, which integrates the multidimensional analysis and sequential data mining. We also thoroughly explore efficient methods for multi-dimensional sequential pattern mining. We examine feasible combinations of efficient sequential pattern mining and multi-dimensional analysis methods, as well as develop uniform methods for high-performance mining. Extensive experiments show the advantages as well as limitations of these methods. Some recommendations on selecting proper method with respect to data set properties are drawn.
Efficient and Robust Feature Extraction and Pattern Matching of Time Series by a Lattice Structure
Authors: Wan Po Man Polly, Man Hon Wong
Venue: CIKM
Year: 2001

The efficiency of searching scaling-invariant and shifting-invariant shapes in a set of massive time series data can be improved if searching is performed on an approximated sequence which involves less data but contains all the significant features. However, commonly used smoothing techniques, such as moving averages and best-fitting polylines, usually miss important peaks and troughs and deform the time series. In addition, these techniques are not robust, as they often requires users to supply a set of smoothing parameters which has direct effect on the resultant approximation pattern. To address these problems, an algorithm to construct a lattice structure as an underlying framework for pattern matching is proposed in this paper. As inputs, the algorithm takes a time series and users' requirements of level of detail. The algorithm then identifies all the important peaks and troughs (known as controlm points) in the time series and classifies the points into appropriate layers of the lattice structure. The control points in each layer of the structure form an approximation pattern an yet preserve the overall shape of the original series with approximation error lies within certain bound. The lower the layer, the more precise the approximation pattern is. Putting in another way, the algorithm takes different levels of data smoothing into account. Also, the lattice structure can be indexed to further improve the performance of pattern matching.
Automatic Discovery of Salient Segments in Imperfect Speech Transcripts
Authors: Dulce B. Ponceleon, Savitha Srinivasan
Venue: CIKM
Year: 2001

This paper addresses the problem of automatic detection of salient video segments for real-world applications such as corporate training based on associated speech transcriptions. We present a novel segmentation algorithm based on automatic speech recognition (ASR) applied to the audio track of the video. Our feature set consists of word n-grams extracted from the imperfect speech transcriptions. We use a two-pass algorithm that combines a boundary-based method with a content-based method. In the first pass, we analyze the temporal distribution and the rate of arrival of features to compute an initial segmentation. In the second pass, we detect changes in content-bearing words by using the content-bearing features as queries in an information retrieval system. The content-based second pass validates the initial segments and merges them as needed. Variations in the structure of the audio/video content, and the accuracy of ASR have an impact on the feasibility of the segmentation task. For realistic data we observe that we can identify content-rich segments of the audio. In the best scenario a high-level table-of-contents is generated and in the worse scenario a single salient segment is identified. We illustrate the algorithm in detail with some examples and validate the data with manual segmentation boundaries.
Index Filtering and View Materialization in ROLAP Environment
Authors: Shi Guang Qiu, Tok Wang Ling
Venue: CIKM
Year: 2001

Using materialized view to accelerate OLAP queries is one of the most common methods used in ROLAP systems. However, high storage and computation cost make this method very difficult to be implemented in the actual environment. Among various issues associated with this, index selection and view materialization are two of the top challenges. In this paper, we propose to build indexes on subsets of the primary keys rather than the full sets if the index selectivity for these smaller indexes can be maintained above the required level. Based on that we propose an index filtering rule, Dominant Prime (DPrime) Index Set Filter, to filter out candidate indexes that have insufficient index selectivity or have cheaper alternatives. In the second part, we propose a view materialization method, Nested Relation Approach, to group tuples with the same value for index attributes into one super tuple using a nested relation and implement this method using Oracle VARRAY. In performance tests, our method outperforms others significantly.
Mining the Web for Answers to Natural Language Questions
Authors: Dragomir R. Radev, Hong Qi, Zhiping Zheng, Sasha Blair-Goldensohn, Zhu Zhang, Weiguo Fan, John M. Prager
Venue: CIKM
Year: 2001

The web is now becoming one of the largest information and knowledge repositories. Many large scale search engines (Google, Fast, Northern Light, etc.) have emerged to help users find information. In this paper, we study how we can effectively use these existing search engines to mine the Web and discover the "correct" answers to factual natural language questions.We propose a probabilistic algorithm called QASM (Question Answering using Statistical Models) that learns the best query paraphrase of a natural language question. We validate our approach for both local and web search engines using questions from the TREC evaluation. We also show how this algorithm can be combined with another algorithm (AnSel) to produce precise answers to natural language questions.
Approaches to Collection Selection and Results Merging for Distributed Information Retrieval
Authors: Yves Rasolofo, Faïza Abbaci, Jacques Savoy
Venue: CIKM
Year: 2001

We have investigated two major issues in Distributed Information Retrieval (DIR), namely: collection selection and search results merging. While most published works on these two issues are based on pre-stored metadata, the approaches described in this paper involve extracting the required information at the time the query is processed. In order to predict the relevance of collections to a given query, we analyse a limited number of full documents (e.g., the top five documents) retrieved from each collection and then consider term proximity within them. On the other hand, our merging technique is rather simple since input only requires document scores and lengths of results lists. Our experiments evaluate the retrieval effectiveness of these approaches and compare them with centralised indexing and various other DIR techniques (e.g., CORI). We conducted our experiments using two testbeds: one containing news articles extracted from four different sources (2 GB) and another containing 10 GB of Web pages. Our evaluations demonstrate that the retrieval effectiveness of our simple approaches is worth considering.
Efficient Runtime Generation of Association Rules
Authors: Richard Relue, Xindong Wu, Hao Huang
Venue: CIKM
Year: 2001

Mining frequent patterns in transaction databases has been a popular subject in data mining research. Common activities include finding patterns in database transactions, times-series, and exceptions. The Apriori algorithm is a widely accepted method of generating frequent patterns. The algorithm can require many scans of the database and can seriously tax resources. New methods of finding association rules, such as the Frequent Pattern Tree (FP-Tree) have improved performance, but still have problems when new data becomes available and require two scans of the database.This paper proposes a new method, which requires only one scan of the database and supports update of patterns when new data becomes available. We design a new structure called Pattern Repository (PR), which stores all of the relevant information in a highly compact form and allows direct derivation of the FP-Tree and association rules quickly with a minimum of resources. In addition, it supports run-time generation of association rules by considering only those patterns that meet on-line data requirements.
What Can Researches Do to Improve Security of Data and Documents?
Authors: Arnon Rosenthal
Venue: CIKM
Year: 2001

Data security (protection of information rather than systems) goes far beyond the traditional questions of RDBMS grant/revole, or security markings on documents. We will discuss what the new research agenda should be to impact the masses of systems.
Document Release versus Data Access Controls: Two Sides of the Same Coin?
Authors: Arnon Rosenthal, Gio Wiederhold
Venue: CIKM
Year: 2001

The database and document worlds have traditionally had different approaches to security. Databases provide access controls on structured data, while document security interrogates the outgoing information, based on document markings and actual contents. For the emerging world in which many documents are generated from structured data (and vice versa), the separation can cause failure, implementation-dependence, inconsistency, and wasted effort. After comparing approaches and mechanisms in the two areas, we identify issues in security administration and implementation in military and medical applications. We then present elements of a unifying model.
Finding Similar Images Quickly Using Object Shapes
Authors: Heng Tao Shen
Venue: CIKM
Year: 2001

Retrieving images from a large image collection has been an active area of research. Most of the existing works have focused on content representation. In this paper, we address the issue of identifying relevant images quickly. This is important in order to meet the users' performance requirements. We propose a framework for fast image retrieval based on object shapes extracted from objects within images. The framework builds a hierarchy of approximations on object shapes such that shape representation at a higher level is a coarser representation of a shape at the lower level. In other words, multiple shapes at a lower level can be mapped into a single shape at a higher level. In this way, the hierarchy serves to partition the database at various granularities. Given a query shape, by searching only the relevant paths in the hierarchy, a large portion of the database can thus be pruned away. We propose the angle mapping (AM) method to transform a shape from one level to another (higher) level. AM essentially replaces some edges of a shape by a smaller number of edges based on the angles between the edges, thus reducing the complexity of the original shape. Based on the framework, we also propose two hierarchical structures to facilitate speedy retrieval. The first, called Hierarchical Partitioning on Shape Representation (HPSR), uses the shape representation as the indexing key. The second, called Hierarchical Partitioning on Angle Vector (HPAV), captures the angle information from the shape representation. We conducted an extensive study on both methods to see their quality and efficiency. Our experiments on sets of images, each of which has objects around from 1 to 30, showed that the framework can provide speedy image retrieval without sacrificing on the quality. Both proposed schemes can improve the efficiency by as much as hundreds of times to sequential scanning. The improvement grows as image database size, objects per image or object dimension increase.
Query-Sensitive Similarity Measures for the Calculation of Interdocument Relationships
Authors: Anastasios Tombros, C. J. van Rijsbergen
Venue: CIKM
Year: 2001

Abstract. The application of document clustering to information retrieval has been motivated by the potential effectiveness gains postulated by the Cluster Hypothesis. The hypothesis states that relevant documents tend to be highly similar to each other, and therefore tend to appear in the same clusters. In this paper we propose that, for any given query, pairs of relevant documents will exhibit an inherent similarity which is dictated by the query itself. Our research describes an attempt to devise means by which this similarity can be detected. We propose the use of query-sensitive similarity measures that bias interdocument relationships towards pairs of documents that jointly possess attributes that are expressed in a query. We experimentally tested query-sensitive measures against conventional ones that do not take the context of the query into account. We calculated interdocument relationships for varying numbers of top-ranked documents for five document collections. Our results show a consistent and significant increase in the number of relevant documents that become nearest neighbours of any given relevant document when query-sensitive measures are used. These results suggest that the effectiveness of a cluster-based IR system has the potential to increase through the use of query-sensitive similarity measures. 1.
Text Classification in a Hierarchical Mixture Model for Small Training Sets
Authors: Kristina Toutanova, Francine Chen, Kris Popat, Thomas Hofmann
Venue: CIKM
Year: 2001

Documents are commonly categorized into hierarchies of topics, such as the ones maintained by Yahoo! and the Open Directory project, in order to facilitate browsing and other interactive forms of information retrieval. In addition, topic hierarchies can be utilized to overcome the sparseness problem in text categorization with a large number of categories, which is the main focus of this paper. This paper presents a hierarchical mixture model which extends the standard naive Bayes classifier and previous hierarchical approaches. Improved estimates of the term distributions are made by differentiation of words in the hierarchy according to their level of generality/specificity. Experiments on the Newsgroups and the Reuters-21578 dataset indicate improved performance of the proposed classifier in comparison to other state-of-the-art methods on datasets with a small number of positive examples.