OpenRaiser/Intern-Atlas huggingface dataset:
Performance and Implications of Semantic Indexing in a Distributed Environment
Authors: Conrad T. K. Chang, Bruce R. Schatz
Venue: CIKM
Year: 1999

A research prototype is presented for semantic indexing and retrieval in Information Retrieval. The prototype is motivated by a desire to provide a more efficient and effective information retrieval system compared to the current state of the art. An overview of the Interspace architecture layers is discussed. An object model supporting semantic operations is developed. The model contains a rich set of classes and relationships of the data for the semantic indexing module. The basis of our semantic indexing is done by the creation of concept space. A concept space is an index of a collection that uses document statistics to capture the relationships between concepts. It is useful for boosting text search, by term suggestion of alternative terms semantically related to query terms. Over the years, we have developed generic technology for concept spaces computation on large collections across many subjects. Recent computations on discipline-scale collections have been made on high-end supercomputers. This paper describes our implementation and implications of the computation in a distributed computing environment. Experimental results using different collection sizes and number of processes are presented to show the feasibility of this approach. We also show that laboratory and community collections are already easily computable using a group of PCs in a lab via a message-passing model. We conclude that PC clusters will shortly be able to compute semantic indexes for any real collections.
Requirement-Based Data Cube Schema Design
Authors: David Wai-Lok Cheung, Bo Zhou, Ben Kao, Hongjun Lu, Tak Wah Lam, Hing-Fung Ting
Venue: CIKM
Year: 1999

On-line analytical processing (OLAP) requires efficient processing of complex decision support queries over very large databases. It is well accepted that pre-computed data cubes can help reduce the response time of such queries dramatically.Avery important design issue of an efficient OLAP system is therefore the choice of the right data cubes to materialize. We call this problem the data cube schema design problem. In this paper we show that the problem of finding an optimal data cube schema for an OLAP system with limited memory is NP-hard. As a more computationally efficient alternative, we propose a greedy approximation algorithm cMP and its variants. Algorithm cMP consists of two phases. In the first phase, an initial schema consisting of all the cubes required to efficiently answer the user queries is formed. In the second phase, cubes in the initial schema are selectively merged to satisfy the memory constraint. We show that cMP is very effective in prunning the search space for an optimal schema. This leads to a highly efficient algorithm. We report
Word Segmentation and Recognition for Web Document Framework
Authors: Chi-Hung Chi, Chen Ding, Andrew Lim
Venue: CIKM
Year: 1999

It is observed that a better approach to Web information understanding is to base on its document framework, which is mainly consisted of (i) the title and the URL name of the page, (ii) the titles and the URL names of the Web pages that it points to, (iii) the alternative information source for the embedded Web objects, and (iv) its linkage to other Web pages of the same document. Investigation reveals that a high percentage of words inside the document framework are “compound words” which cannot be understood by ordinary dictionaries. They might be abbreviations or acronyms, or concatenations of several (partial) words. To recover the content hierarchy of Web documents, we propose a new word segmentation and recognition mechanism to understand the information derived from the Web document framework. A maximal bi-directional matching algorithm with heuristic rules is used to resolve ambiguous segmentation and meaning in compound words. An adaptive training process is further employed to build a dictionary of recognisable abbreviations and acronyms. Empirical results show that over 75% of the compound words found in the Web document framework can be understood by our mechanism. With the training process, the success rate of recognising compound words can be increased to about 90%.
Binary String Relations: A Foundation for Spatiotemporal Knowledge Representation
Authors: Vasilis Delis, Thanasis Hadzilacos
Venue: CIKM
Year: 1999

The paper is concerned with the qualitative representation of spatiotemporal relations. We initially propose a multiresolution framework for the representation of relations among 1D intervals, based on a binary string encoding. We subsequently extend this framework to multiple dimensions, thus allowing the description of spatiotemporal relations at various contexts. The feasible relations at a particular resolution level are inherently permeated by a poset structure, called conceptual neighbourhood, upon which we propose efficient relation inferencing mechanisms. Finally, we discuss the application of our model to spatiotemporal reasoning, which refers to the classic problems of satisfiability and deductive closure of a set of spatiotemporal assertions.
Practical evaluation of IR within automated classification systems
Authors: Ron Dolin, J. Pierre, M. Butler, R. Avedon
Venue: CIKM
Year: 1999

This paper describes some of the work we have done to evaluate and compare the use of three IR systems (Verity, LSI, and SMART) as black boxes within an automated classification environment. We use automated classification to make a quantitative comparison of the effectiveness of the systems within this context. In so doing, we also develop criteria for the construction of a useful training set. These results lead to metrics useful in the integration of IR systems into larger applications. We conclude with an initial API for an IR component within an automated classification architecture.
A Multiple-Resolution Method for Edge-Centric Data Clustering
Authors: Scott Epter, Mukkai S. Krishnamoorthy
Venue: CIKM
Year: 1999

Recent works in spatial data clustering view the input data set in terms of inter-point edge lengths rather than the points themselves. Cluster detection in such a system is a matter of finding connected paths of edges whose weight is no greater than some user input threshold or cutoff value. The SMTIN algorithm[9] is one such system that uses Delaunay triangulation to compute the set of nearest neighbor edges quickly and efficiently. Experiments demonstrate a substantial performance and accuracy improvement using SMTIN in comparison to other clustering systems.
Mining Inter-Transaction Associations with Templates
Authors: Ling Feng, Hongjun Lu, Jeffrey Xu Yu, Jiawei Han
Venue: CIKM
Year: 1999

Multi-dimensional, inter-transaction association rules extend the traditional association rules to describe more general associations among items with multiple properties cross transactions. “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away” is an example of such rules. Since the number of potential inter-transaction association rules tends to be extremely large, mining inter-transaction associations poses more challenges on efficient processing than mining intra-transaction associations. In order to make such association mining truly practical and computationally tractable, in this study, we present a template model to help users declare the interesting inter-transaction associations to be mined. With the guidance of templates, several optimization techniques are devised to speed up the discovery of inter-transaction association rules. We show, through a series of experiments, that these optimization techniques can yield significant performance benefits.
Clustering Declustered Data for Efficient Retrieval
Authors: Hakan Ferhatosmanoglu, Divyakant Agrawal, Amr El Abbadi
Venue: CIKM
Year: 1999

Modern databases increasingly integrate new kinds of information, such as multimedia information in the form of image, video, and audio data. Both the dimensionality and the amount of data that need to be processed is increasing rapidly, increasing the demand for the efficient retrieval of large amounts of multi-dimensional data. Declustering techniques for multi-disk architectures have been effectively used for storage. In this paper, we first establish that besides exploiting the parallelism, a careful organization of each disk must be considered for fast searching. We introduce the notion of page allocation and data space mapping which can be used to organize and retrieve multidimensional data. We develop these notions based on three different partitioning strategies: regular grid partitioning, concentric hypercubes and hyperpyramids. We develop techniques that satisfy efficient retrieval by optimizing the number of buckets retrieved by the query, disk arm movement and I/O parallelism. We prove that concentric hypercube-based mapping satisfies the optimal clustering and optimal parallelism. We develop a technique based on hyperpyramid partitioning that reduces the number of buckets retrieved by the query and has efficient inter- and intra-disk organizations. We evaluate the performance of proposed techniques by comparing them with the current approaches. The new techniques lead to very significant improvement over the existing techniques, and result in fast retrieval of multi-dimensional data.
Obsolescent Materialized Views in Query Processing of Enterprise Information Systems
Authors: Avigdor Gal
Venue: CIKM
Year: 1999

In recent years, query processing has become more complex as data sources are frequently replicated and data are periodically processed and embedded within several data sources simultaneously. These trends have necessitated the optimization of techniques for query processing in order to exploit these new alternatives. Accordingly, this paper introduces an improved query optimization technique, which is capable of assessing query plans that use both current and obsolescent data. In particular, we provide a cost model by which the trade-offs of using obsolescent materialized views can be evaluated and we also discuss the method's applicability to contemporary query optimization techniques.
Browsing Large Digital Library Collections Using Classification Hierarchies
Authors: Steven Geffner, Divyakant Agrawal, Amr El Abbadi, Terence R. Smith
Venue: CIKM
Year: 1999

Summarization of intermediary query result sets plays an important role when users browse through digital library collections. Summarization enables users to quickly digest the results of their queries, and provides users with important information they can use to narrow their search interactively. Techniques from the field of data analysis may be applied to the problem of generating summaries of query results efficiently. Such techniques should permit the incorporation of classification hierarchies in order to provide powerful browsing environments for digital library users.
A Comparison of Alternative Continuous Display Techniques with Heterogeneous Multi-Zone Disks
Authors: Shahram Ghandeharizadeh, Seon Ho Kim
Venue: CIKM
Year: 1999

A number of recent technological trends have made data intensive applications such as continuous media (audio and video) servers a reality. These servers are expected to play an important role in applications such as video-on-demand, digital library, news-on-demand, distance learning, etc. Continuous media applications are data intensive and might require storage subsystems that consist of hundreds of (multi-zone) disk drives. With the current technological trends, a homogeneous disk subsystem might evolve to consist of a heterogeneous collection of disk drives. Given such a storage subsystem, the system must continue to support a hiccup-free display of audio and video clips. This study describes extensions of four continuous display techniques for multi-zone disk drives to a heterogeneous platform. These techniques include IBM's Logical Track [21], HP's Track Pairing [4], and USC's FIXB [9] and deadline driven techniques [10]. We quantify the performance tradeoff associated with these techniques using analytical models and simulation studies. The obtained results demonstrate tradeoffs between the cost per simultaneous stream supported by a technique, the wasted disk space, and the incurred startup latency.
Searching the Web: Can You Find What You Want?
Authors: C. Lee Giles
Venue: CIKM
Year: 1999

The World Wide Web has revolutionized communication and information distribution, storage, and access. Its impact has been felt everywhere - e.g. science and technology, commerce and business, education, government, religion, law, entertainment, health care. Even so, there are many ways the web can be improved. We discuss what the web consists of and how it has changed, what is the size of the web, and what is covered. Results for the publicly indexable web show that the web though Terabytes in size and growing is still less than large commercial databases and the Library of Congress. Though the web started out as an academic-government endeavor, it is now primarily commerce. Furthermore, the major web search engines cover only a fraction of the publicly indexable web and appear to base their indexing strategy on the popularity of information. Since current search on the web is primarily done with the search engines, what would be the economic, political and scientific implications of these results?
A Probabilistic Description-Oriented Approach for Categorizing Web Documents
Authors: Norbert Gövert, Mounia Lalmas, Norbert Fuhr
Venue: CIKM
Year: 1999

The automatic categorisation of web documents is becoming crucial for organising the huge amount of information available in the Internet. We are facing a new challenge due to the fact that web documents have a rich structure and are highly heterogeneous. Two ways to respond to this challenge are (1) using a representation of the content of web documents that captures these two characteristics and (2) using more effective classifiers.
Efficient Mining of Association Rules in Text Databases
Authors: John D. Holt, Soon Myoung Chung
Venue: CIKM
Year: 1999

In this paper, we propose two new algorithms for mining association rules between words in text databases. The characteristics of text databases are quite different from those of retail transaction databases, and existing mining algorithms cannot handle text databases efficiently because of the large number of itemsets (i.e., words) that need to be counted. Two well-known mining algorithms, Apriori algorithm and Direct Hashing and Pruning (DHP) algorithm, are evaluated in the context of mining text databases, and are compared with the new proposed algorithms named Multipass-Apriori (M-Apriori) and Multipass-DHP (M-DHP). It has been shown that the proposed algorithms have better performance for large text databases.
Classification Algorithms for NETNEWS Articles
Authors: Wen-Lin Hsu, Sheau-Dong Lang
Venue: CIKM
Year: 1999

We propose several algorithms using the vector space model to classify the news articles posted on the NETNEWS according to the newsgroup categories. The baseline method combines the terms of all the articles of each newsgroup in the training set to represent the newsgroups as single vectors. After training, the incoming news articles are classified based on their similarity to the existing newsgroup categories. We propose to use the following techniques to improve the classification performance of the baseline method: (1) use routing (classification) accuracy and the similarity values to refine the training set; (2) update the underlying term structures periodically during testing; and (3) apply k-means clustering to partition the newsgroup articles and represent each newsgroup by k vectors. Our test collection consists of the real news articles and the 519 subnewsgroups under the REC newsgroup of NETNEWS in a period of 3 months. Our experimental results demonstrate that the technique of refining the training set reduces from one-third to two-thirds of the storage. The technique of periodical updates improves the routing accuracy ranging from 20% to 100% but incurs runtime overhead. Finally, representing each newsgroup by k vectors (with k = 2 or 3) using clustering yields the most significant improvement in routing accuracy, ranging from 60% to 100%, while causing only slightly higher storage requirements.
Indexing Techniques for Wireless Data Broadcast Under Data Clustering and Scheduling
Authors: Qinglong Hu, Wang-Chien Lee, Dik Lun Lee
Venue: CIKM
Year: 1999

This paper investigates power conserving indexing techniques for data disseminated on a broadcast channel. A hybrid indexing method combining strengths of the signature and the index tree techniques is presented. Different from previous studies, our research takes into consideration two important data organization factors, namely, clustering and scheduling. Cost models for index, signature and hybrid methods are derived by taking into account various data organizations accommodating these two factors. Based on our analytical comparisons, the signature and the hybrid indexing techniques are the best choices for power conserving indexing of various data organizations on wireless broadcast channels.
An Effective Mechanism for Index Update in Structured Documents
Authors: Hyunchul Jang, Youngil Kim, Dongwook Shin
Venue: CIKM
Year: 1999

Indexing and retrieval of structured documents have been drawing attention increasingly since they enable to retrieve and access a certain part of a document easily. So far, several methods have been proposed in the setting that documents are rarely changed. These can be applied for the books or journals possessed in libraries, but hardly work for the documents that are subject to change frequently in the business domain. This paper aims at enabling incremental update of indices whenever parts of documents are changed. For this, it employs the index-organized table that has been developed for the full-text retrieval in Oracle. It creates several index-organized tables that are essential in implementing the Bottom Up Scheme strategy, which has been developed for manipulating structured documents efficiently.Along with an experiment, the technique presented here does not add much index overhead to the original one taken to the index organized table. In addition, the updates of indices are performed quickly as soon as parts of documents are changed.
Extending Complex Ad-Hoc OLAP
Authors: Theodore Johnson, Damianos Chatziantoniou
Venue: CIKM
Year: 1999

Large scale data analysis and mining activities require sophisticated information extraction queries. Many queries require complex aggregation, and many of these aggregates are non-distributive. Conventional solutions to this problem involve defining User Defined Aggregate Functions (UDAFs). However, the use of UDAFs entails several problems. Defining a new UDAF can be a significant burden for the user, and optimizing queries involving UDAFs is difficult because of the “black box” nature of the UDAF.
A Method of Geographical Name Extraction from Japanese Text for Thematic Geographical Search
Authors: Yasusi Kanada
Venue: CIKM
Year: 1999

A text retrieval method called the thematic geographical search method has been developed and applied to a Japanese encyclopedia called the World Encyclopædia. In this method, the user specifies a search theme using free words, then obtains a sorted list of excerpts and hyperlinks to encyclopedia sentences that contain geographical names. Using this list, the user can also open maps that indicate the locations of the names. To generate an index of names for this searching, a method of extracting geographical names has been developed. In this method, geographical names are extracted, matched to names in a geographical name database, and identified. Geographical names, however, often have several types of ambiguities. Ambiguities are resolved by using non-local context analysis, which uses a stack and several other techniques. As a result, the precision of extracted names is more than 96% on average. This method depends on features of the Japanese language, but the strategy and most of the techniques can be applied to texts in English or other languages.
Indexing field values in field oriented systems: interval Quadtree
Authors: Myoung-Ah Kang, Sylvie Servigne, Ki-Joune Li, Robert Laurini
Venue: CIKM
Year: 1999

With the extension of spatial database applications, field oriented systems emerge as an important research issue in order to deal with continuous natural phenomena during the last years. It however has a large volume of data and efficient indexing methods for field data are necessary to overcome the performance obstacle. In special, we introduce indexing methods for field value queries (i.e. searching some regions where the temperature is more 20 degrees). We introduce the concept of subfield and show how we make use of this concept to index field values in field oriented systems. We present two implementation methods based on Quadtree space subdivision. We modify traditional linear quadtree implementation method for field value query processing using subfields. We analyze the performance of our methods. Experimentation with real terrain data shows that proposed indexing methods improve the query processing time of field value queries in comparison with the case of no indexing method.
Updates and View Maintenance in Soft Real-Time Database Systems
Authors: Ben Kao, Kam-yiu Lam, Brad Adelberg, Reynold Cheng, Tony S. H. Lee
Venue: CIKM
Year: 1999

A database system contains base data items which record and model a physical, real world environment. For better decision support, base data items are summarized and correlated to derive views. These base data and views are accessed by application transactions to generate the ultimate actions taken by the system. As the environment changes, updates are applied to the base data, which subsequently trigger view recomputations. There are thus three types of activities: base data update, view recomputation, and transaction execution. In a real-time system, two timing constrains need to be enforced. We require transactions meet their deadlines (transaction timeliness) and read fresh data (data timeliness). In this paper we define the concept of absolute and relative temporal consistency from the perspective of transactions. We address the important issue of transaction scheduling among the three types of activities such that the two timing requirements can be met. We also discuss how a real-time database system should be designed to enforce different levels of temporal consistency.
Spatial Match Representation Scheme Supporting Ranking in Iconic Images Databases
Authors: Yeon-Jung Kim, Choon-Bo Shim, Jae-Woo Chang
Venue: CIKM
Year: 1999

Because content-based image retrieval is essential to retrieve relevant multimedia documents, we represent images as a set of recognizable symbols, i.e., icon objects, and do indexing by regarding the icon object as a representative of a given document. When users request content-based image retrieval, we convert a query image into icon objects and retrieve relevant images in the database. In this paper, we propose a new spatial-match representation scheme, called SRR(Spatial-match Representation supporting Ranking) scheme, which combine directional operators with positional operators. Therefore, our SRR scheme can represent spatial relationships between icon objects precisely and can provide ranking for the retrieved images. In addition, we compare our scheme with the conventional 9DLT and SMR schemes in terms of retrieval effectiveness. Finally, we show from our experiment that our SRR scheme holds about 25% higher recall and about 10% higher precision, compared with the 9DLT and the SMR.