OpenRaiser/Intern-Atlas huggingface dataset:
Searching web databases by structuring keyword-based queries
Authors: Pável Calado, Altigran Soares da Silva, Rodrigo C. Vieira, Alberto H. F. Laender, Berthier A. Ribeiro-Neto
Venue: CIKM
Year: 2002

On-line information services have become widespread in the Web nowadays. However, Web users are non-specialized and have a great variety of interests. Thus, interfaces for Web databases must be simple and uniform. In this paper we present an approach, based on Bayesian networks, for querying Web databases using keywords only. According to this approach, the user inputs a query through a simple search-box interface. From the input query, one or more plausible structured queries are derived and submitted to Web databases. The results are then retrieved and presented to the user as ranked answers. Our approach reduces the complexity of existing on-line interfaces and offers a solution to the problem of querying several distinct Web databases with a single interface. The applicability of the proposed approach was demonstrated by experimental results with 3 databases, obtained with a prototype search system that implements it. We have found that from 77% to 95% of the time, one of the top three resulting structured queries is the proper one. Further, when the user selects one of these three top queries for processing, the ranked answers present average precision figures from 60% to about 100%.
F4: large-scale automated forecasting using fractals
Authors: Deepayan Chakrabarti, Christos Faloutsos
Venue: CIKM
Year: 2002

Forecasting has attracted a lot of research interest, with very successful methods for periodic time series. Here, we propose a fast, automated method to do non-linear forecasting, for both periodic as well as chaotic time series. We use the technique of delay coordinate embedding, which needs several parameters; our contribution is the automated way of setting these parameters, using the concept of `intrinsic dimensionality'. Our operational system has fast and scalable algorithms for preprocessing and, using R-trees, also has fast methods for forecasting. The result of this work is a black-box which, given a time series as input, finds the best parameter settings, and generates a prediction system. Tests on real and synthetic data show that our system achieves low error, while it can handle arbitrarily large datasets.
A new cache replacement algorithm for the integration of web caching and prefectching
Authors: Cheng-Yue Chang, Ming-Syan Chen
Venue: CIKM
Year: 2002

Web caching and Web prefetching are two important techniques to reduce the noticeable response time perceived by users. Note that by integrating Web caching and Web prefetching, these two techniques can complement each other since Web caching technique exploits the temporal locality whereas Web prefetching technique utilizes the spatial locality of Web objects. However, without circumspect design, the integration of these two techniques might cause significant performance degradation to each other. In view of this, we propose in this paper an innovative cache replacement algorithm, which not only considers the caching effect in the Web environment but also evaluates the prefetching rules provided by various prefetching schemes. Specifically, we formulate a normalized profit function to evaluate the profit from caching an object (i.e., either a non-implied object or an implied object according to some prefetching rule). Based on the normalized profit function devised, we devise an innovative Web cache replacement algorithm, referred to as algorithm IWCP (standing for the Integration of Web Caching and Prefetching). Using an event-driven simulation, we evaluate the performance of algorithm IWCP under several circumstances. The experimental results show that algorithm IWCP consistently outperforms the companion schemes in various performance metrics.
On the efficient evaluation of relaxed queries in biological databases
Authors: Yangjun Chen, Dunren Che, Karl Aberer
Venue: CIKM
Year: 2002

Abstract In this paper, a new technique is developed to support the query relaxation in biological databases. Query relaxation is required due to the fact that queries tend not to be expressed exactly by the users, especially in scientific databas s such as biological databases, in which complex domain knowledge is heavily involved. To treat this problem, we propose the concept of the socalled fuzzy equivalence classes to capture important kinds of domain knowledge that is used to relax queries. This concept is further integrated with the canonical techniques for pattern searching such as the position tree and automaton theory. As a result, fuzzy queries produced through relaxation can be efficiently evaluated. This method has been successfully utilized in a practical biological database- the GPCRDB.
XKvalidator: a constraint validator for XML
Authors: Yi Chen, Susan B. Davidson, Yifeng Zheng
Venue: CIKM
Year: 2002

The role of XML in data exchange is evolving from one of merely conveying the structure of data to one that also conveys its semantics. In particular, several proposals for key and foreign key constraints have recently appeared, and aspects of these proposals have been adopted within XMLSchema.In this paper, we examine the problem of checking keys and foreign keys in XML documents using a validator based on SAX. The algorithm relies on an indexing technique based on the paths found in key definitions, and can be used for checking the correctness of an entire document (bulk checking) as well as for checking updates as they are made to the document (incremental checking). The asymptotic performance of the algorithm is linear in the size of the document or update. Furthermore, experimental results demonstrate reasonable performance.
I/O-efficient techniques for computing pagerank
Authors: Yen-Yu Chen, Qingqing Gan, Torsten Suel
Venue: CIKM
Year: 2002

Over the last few years, most major search engines have integrated link-based ranking techniques in order to provide more accurate search results. One widely known approach is the Pagerank technique, which forms the basis of the Google ranking scheme, and which assigns a global importance measure to each page based on the importance of other pages pointing to it. The main advantage of the Pagerank measure is that it is independent of the query posed by a user; this means that it can be precomputed and then used to optimize the layout of the inverted index structure accordingly. However, computing the Pagerank measure requires implementing an iterative process on a massive graph corresponding to billions of web pages and hyperlinks.In this paper, we study I/O-efficient techniques to perform this iterative computation. We derive two algorithms for Pagerank based on techniques proposed for out-of-core graph algorithms, and compare them to two existing algorithms proposed by Haveliwala. We also consider the implementation of a recently proposed topic-sensitive version of Pagerank. Our experimental results show that for very large data sets, significant improvements over previous results can be achieved on machines with moderate amounts of memory. On the other hand, at most minor improvements are possible on data sets that are only moderately larger than memory, which is the case in many practical scenarios.
Categorizing information objects from user access patterns
Authors: Mao Chen, Andrea S. LaPaugh, Jaswinder Pal Singh
Venue: CIKM
Year: 2002

Many web sites have dynamic information objects whose topics change over time. Classifying these objects automatically and promptly is a challenging and important problem for site masters. Traditional content-based and link structure based classification techniques have intrinsic limitations for this task. This paper proposes a framework to classify an object into an existing category structure by analyzing the users' traversals in the category structure. The key idea is to infer an object's topic from the predicted preferences of users when they access the object. We compare two approaches using this idea. One analyzes collective user behavior and the other each user's accesses. We present experimental results on actual data that demonstrate a much higher prediction accuracy and applicability with the latter approach. We also analyze the correlation between classification quality and various factors such as the number of users accessing the object. To our knowledge, this work is the first effort in combining object classification with user access prediction.
A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B±trees
Authors: Eugene Inseok Chong, Jagannathan Srinivasan, Souripriya Das, Chuck Freiwald, Aravind Yalamanchi, Mahesh Jagannath, Anh-Tuan Tran, Ramkumar Krishnan, Richard Jiang
Venue: CIKM
Year: 2002

Any auxiliary structure, such as a bitmap or a B+-tree index, that refers to rows of a table stored as a primary B+-tree (e.g., tables with clustered index in Microsoft SQL Server, or index-organized tables in Oracle) by their physical addresses would require updates due to inherent volatility of those addresses. To address this problem, we propose a mapping mechanism that 1) introduces a single mapping table, with each row holding one key value from the primary B+-tree, as an intermediate structure between the primary B+-tree and the associated auxiliary structures, and 2) augments the primary B+-tree structure to include in each row the physical address of the corresponding mapping table row. The mapping table row addresses can then be used in the auxiliary structures to indirectly refer to the primary B+-tree rows. The two key benefits are: 1) the mapping table shields the auxiliary structures from the volatility of the primary B+-tree row addresses, and 2) the method allows reuse of existing conventional table mechanisms for supporting auxiliary structures on primary B+-trees. The mapping mechanism is used for supporting bitmap indexes on index-organized tables in Oracle9i. The analytical and experimental studies show that the method is storage efficient, and (despite the mapping table overhead) provides performance benefits that are similar to those provided by bitmap indexes implemented on conventional tables.
The verity federated infrastructure
Authors: Kiam Choo, Rajat Mukherjee, Rami Smair, Wei Zhang
Venue: CIKM
Year: 2002

In the course of researching a subject, it is often necessary to submit the same search request to multiple heterogeneous information sources in order to (a) aggregate as much information as possible, and (b) integrate different aspects of the subject into a coherent report. While it is clear that there is value in providing a federated search solution to make dealing with multiple sources less time-consuming, not all organizations aggregate from the same sources, and once the information has been retrieved, not all organizations want them to be integrated in the same way.The Verity Federated Infrastructure addresses this problem by providing a flexible framework for adding new sources and customizing the way in which results are integrated, post-processed and presented. A new source is made available by writing a Java module called a worker that abides by the search interface of the source. Sources can range from simple information feeds to more complex applications, e.g., CRM systems, relational databases, etc. Workers also perform post-processing on the results returned by other workers, e.g., to provide uniform scores for results from different sources, filtering, etc. This post-processing enables different results to be integrated into a coherent report. Post-processing is triggered by events that propagate between workers and is done asynchronously in the background while results are being viewed. This ability to do background post-processing allows execution of time-consuming operations that provide substantial value without adversely affecting user experience. Finally, search results are returned and viewed incrementally, which enables searching of peer-to-peer networks via peer workers that we have developed.
Topic-oriented collaborative crawling
Authors: Chiasen Chung, Charles L. A. Clarke
Venue: CIKM
Year: 2002

A major concern in the implementation of a distributed Web crawler is the choice of a strategy for partitioning the Web among the nodes in the system. Our goal in selecting this strategy is to minimize the overlap between the activities of individual nodes. We propose a topic-oriented approach, in which the Web is partitioned into general subject areas with a crawler assigned to each. We examine design alternatives for a topic-oriented distributed crawler, including the creation of a Web page classifier for use in this context. The approach is compared experimentally with a hash-based partitioning, in which crawler assignments are determined by hash functions computed over URLs and page contents. The experimental evaluation demonstrates the feasibility of the approach, addressing issues of communication overhead, duplicate content detection, and page quality assessment.
Thematic mapping - from unstructured documents to taxonomies
Authors: Christina Yip Chung, Raymond Lieu, Jinhui Liu, Alpha K. Luk, Jianchang Mao, Prabhakar Raghavan
Venue: CIKM
Year: 2002

Verity Inc. has developed a comprehensive suite of tools for accurately and efficiently organizing enterprise content which involves four basic steps: (i) creating taxonomies, (ii) building classification models, (iii) populating taxonomies with documents, and (iv) deploying populated taxonomies in enterprise portals. A taxonomy is a hierarchical representation of categories. A taxonomy provides a navigation structure for exploring and understanding the underlying corpus without sifting through a huge volume of documents. Thematic Mapping automatically discovers a concept tree from a corpus of unstructured documents and assigns meaningful labels to concepts based on a semantic network. Integrating with Verity Intelligent Classifier's user-friendly GUI, a user can drill down a concept tree for navigation, perform a conceptual search to retrieve documents pertaining to a concept, build a taxonomy from the concept tree, as well as edit a taxonomy to tailor it into various views (customized taxonomies) of the same corpus. Classification rules can be generated automatically from concepts. These classification rules can be used for populating documents into the taxonomy.
Detecting similar documents using salient terms
Authors: James W. Cooper, Anni Coden, Eric W. Brown
Venue: CIKM
Year: 2002

We describe a system for rapidly determining document similarity among a set of documents obtained from an information retrieval (IR) system. We obtain a ranked list of the most important terms in each document using a rapid phrase recognizer system. We store these in a database and compute document similarity using a simple database query. If the number of terms found to not be contained in both documents is less than some predetermined threshold compared to the total number of terms in the document, these documents are determined to be very similar. We compare this to the shingles approach.
Automatically classifying database workloads
Authors: Said Elnaffar, T. Patrick Martin, Randy Horman
Venue: CIKM
Year: 2002

The type of the workload on a database management system (DBMS) is a key consideration in tuning the system. Allocations for resources such as main memory can be very different depending on whether the workload type is Online Transaction Processing (OLTP) or Decision Support System (DSS). In this paper, we present an approach to automatically identifying a DBMS workload as either OLTP or DSS. We build a classification model based on the most significant workload characteristics that differentiate OLTP from DSS, and then use the model to identify any change in the workload type. We construct a workload classifier from the Browsing and Ordering profiles of the TPC-W benchmark. Experiments with an industry-supplied workload show that our classifier accurately identifies the mix of OLTP and DSS work within an application workload.
Future directions in data mining: streams, networks, self-similarity and power laws
Authors: Christos Faloutsos
Venue: CIKM
Year: 2002

How to spot abnormalities in a stream of temperature data from a sensor? Or from a network of sensors? How does the Internet look like? Are there 'abnormal' sub-graphs in a given social network, possibly indicating, e.g., money-laundering rings?We present some recent work and list many remaining challenges for these two fascinating issues in data mining, namely, streams and networks. Streams appear in numerous settings, in the form of, e.g., temperature readings, road traffic data, series of video frames for surveillance, patient physiological data. In all these settings, we want to equip the sensors with nimble, but powerful enough algorithms to look for patterns and abnormalities,
AuGEAS: authoritativeness grading, estimation, and sorting
Authors: Ayman Farahat, Geoffrey Nunberg, Francine Chen
Venue: CIKM
Year: 2002

When searching for content in in a large heterogeneous document collections like the World Wide Web it is not easy to know which documents provide reliable authoritative information about a subject. The problem is particularly pointed as it concerns content search for "high-value" informational needs such as retrieving medical information, where the cost of error may be high. In this paper, a method is described for estimating the authoritativeness of a document based on textual, non-topical cues. This method is complementary to estimates of authoritativeness based on link structure, such as the PageRank and HITS algorithms. This method is particularly suited to "high-value" content search where the user is interested in searching for information about a specific topic. A method for combining textual estimates of authoritativeness with link analysis is also presented. The types of textual cues to authoritativeness that are easily computed and utilized by our method are described, as well as the method used to select a subset of cues to increase the computation speed. Methods for applying authoritativeness estimates to re-ranking documents returned from search engines, combining textual authoritativeness with social authority, and use in query expansion are also presented. By combining textual authority with link analysis, a more complete and robust estimate can be made of a document's authoritativeness.
Query processing of streamed XML data
Authors: Leonidas Fegaras, David Levine, Sujoe Bose, Vamsi Chaluvadi
Venue: CIKM
Year: 2002

We are addressing the efficient processing of continuous XML streams, in which the server broadcasts XML data to multiple clients concurrently through a multicast data stream, while each client is fully responsible for processing the stream. In our framework, a server may disseminate XML fragments from multiple documents in the same stream, can repeat or replace fragments, and can introduce new fragments or delete invalid ones. A client uses a light-weight database based on our proposed XML algebra to cache stream data and to evaluate XML queries against these data. The synchronization between clients and servers is achieved through annotations and punctuations transmitted along with the data streams. We are presenting a framework for processing XML queries in XQuery form over continuous XML streams. Our framework is based on a novel XML algebra and a new algebraic optimization framework based on query decorrelation, which is essential for non-blocking stream processing.
On scalable information retrieval systems
Authors: Ophir Frieder
Venue: CIKM
Year: 2002

Implementing scalable information retrieval systems requires the design and development of efficient methods to ingest data from multiple sources, search and retrieve results from both English and foreign language document collections and from collections comprising of multiple data types, harness high performance computer technology, and accurately answer user questions. Some recent efforts related to the development of scalable information retrieval systems are described. Particular emphasis is placed on those efforts that were adopted into commercial use.
Index compression vs. retrieval time of inverted files for XML documents
Authors: Norbert Fuhr, Norbert Gövert
Venue: CIKM
Year: 2002

Query languages for retrieval of XML documents allow for conditions referring both to the content and the structure of documents. In this paper, we investigate two different approaches for reducing index space of inverted files for XML documents. First, we consider methods for compressing index entries. Second, we develop the new XS tree data structure which contains the structural description of a document in a rather compact form, such that these descriptions can be kept in main memory. Experimental results on two large XML document collections show that very high compression rates for indexes can be achieved, but any compression increases retrieval time. On the other hand, highly compressed indexes may be feasible for applications where storage is limited, such as in PDAs or E-book devices.
XMLTM: efficient transaction management for XML documents
Authors: Torsten Grabs, Klemens Böhm, Hans-Jörg Schek
Venue: CIKM
Year: 2002

A common approach to storage and retrieval of XML documents is to store them in a database, together with materialized views on their content. The advantage over "native" XML storage managers seems to be that transactions and concurrency are for free, next to other benefits. But a closer look and preliminary experiments reveal that this results in poor performance of concurrent queries and updates. The reason is that database lock contention hinders parallelism unnecessarily. We therefore investigate concurrency control at the semantic, i.e., XML level and describe a respective transaction manager XMLTM. It features a new locking protocol DGLOCK. It generalizes the protocol for locking on directed acyclic graphs by adding simple predicate locking on the content of elements, e.g., on their text. Instead of using the original XML documents, we propose to take advantage of an abstraction of the XML document collection known as DataGuides. XMLTM allows to run XML processing at the underlying database at low ANSI isolation degrees and to release database locks early without sacrificing correctness in this setting. We have built a complete prototype system that is implemented on top of the XML Extender for IBM DB2. Our evaluation shows that our approach consistently yields performance improvements by an order of magnitude. We stress that our approach can also be implemented within a native XML storage manager, and we expect even better performance.
Discovering approximate keys in XML data
Authors: Gösta Grahne, Jianfei Zhu
Venue: CIKM
Year: 2002

Keys are very important in many aspects of data management, such as guiding query formulation, query optimization, indexing, etc. We consider the situation where an XML document does not come with key definitions, and we are interested in using data mining techniques to obtain a representation of the keys holding in a document. In order to have a compact representation of the set of keys holding in a document, we define a partial order on the set of all key expressions. This order is based on an analysis of the properties of absolute and relative keys for XML. Given the existence of the partial order, only a reduced set of key expressions need to be discovered.Due to the semistructured nature of XML documents, it turns out to be useful to consider keys that hold in "almost" the whole document, that is, they are violated only in a small part of the document. To this end, the support and confidence of a key expression are also defined, and the concept of approximate key expression is introduced. We give an efficient algorithm to mine a reduced set of approximate keys from an XML document.