OpenRaiser/Intern-Atlas huggingface dataset:
Efficient and effective server-sided distributed clustering
Authors: Hans-Peter Kriegel, Martin Pfeifle
Venue: CIKM
Year: 2005

Clustering has become an increasingly important task in modern application domains where the data are originally located at different sites. In order to create a central clustering, all clients have to transmit their data to a central server. Due to technical limitations and security aspects, at the central site often only vague object descriptions are available. The server then has to carry out the clustering based on vague and uncertain data. In a recent paper, an approach for clustering uncertain data was proposed based on the concept of medoid clusterings. The idea of this approach is to create first several sample clusterings. Then based on suitable distance functions between clusterings the most average clustering, i.e. the medoid clustering, was determined. In this paper, we extend this approach for partitioning clustering algorithms and propose to compute a centroid clustering based on these input sample clusterings. These centroid clusterings are new artificial clusterings which minimize the distance to all the sample clusterings.
On the estimation of frequent itemsets for data streams: theory and experiments
Authors: Pierre-Alain Laur, Richard Nock, Jean-Emile Symphor, Pascal Poncelet
Venue: CIKM
Year: 2005

In this paper, we devise a method for the estimation of the true support of itemsets on data streams, with the objective to maximize one chosen criterion among {precision, recall} while ensuring a degradation as reduced as possible for the other criterion. We discuss the strengths, weaknesses and range of applicability of this method that relies on conventional uniform convergence results, yet guarantees statistical optimality from different standpoints.
Detecting changes on unordered XML documents using relational databases: a schema-conscious approach
Authors: Erwin Leonardi, Sourav S. Bhowmick
Venue: CIKM
Year: 2005

Several relational approaches have been proposed to detect the changes to XML documents by using relational databases. These approaches store the XML documents in the relational database and issue SQL queries (whenever appropriate) to detect the changes. All of these relational-based approaches use the schema-oblivious XML storage strategy for detecting the changes. However, there is growing evidence that schema-conscious storage approaches perform significantly better than schema-oblivious approaches as far as XML query processing is concerned. In this paper, we study a relational-based unordered XML change detection technique (called H<small>ELIOS</small>) that uses a schema-conscious approach (Shared-Inlining) as the underlying storage strategy. H<small>ELIOS</small> is up to 52 times faster than X-Diff [7] for large datasets (more than 1000 nodes). It is also up to 6.7 times faster than X<small>ANDY</small> [4]. The result quality of deltas detected by H<small>ELIOS</small> is comparable to the result quality of deltas detected by XANDY.
Fast on-line index construction by geometric partitioning
Authors: Nicholas Lester, Alistair Moffat, Justin Zobel
Venue: CIKM
Year: 2005

Inverted index structures are the mainstay of modern text retrieval systems. They can be constructed quickly using off-line merge-based methods, and provide efficient support for a variety of querying modes. In this paper we examine the task of on-line index construction -- that is, how to build an inverted index when the underlying data must be continuously queryable, and the documents must be indexed and available for search as soon they are inserted. When straightforward approaches are used, document insertions become increasingly expensive as the size of the database grows. This paper describes a mechanism based on controlled partitioning that can be adapted to suit different balances of insertion and querying operations, and is faster and scales better than previous methods. Using experiments on 100GB of web data we demonstrate the efficiency of our methods in practice, showing that they dramatically reduce the cost of on-line index construction.
Text document clustering based on frequent word sequences
Authors: Yanjun Li, Soon Myoung Chung
Venue: CIKM
Year: 2005

In this paper, we propose a new text clustering algorithm, named Clustering based on Frequent Word Sequences (CFWS). A word sequence is frequent if it occurs in more than certain percentage of the documents in the text database. In the past, the vector space model was commonly used for information retrieval, but it treats documents as bags of words, ignoring the sequential pattern of word occurrences in the documents. However, the meaning of natural languages strongly depends on the word sequences, and the frequent word sequences can provide compact and valuable information about the text database. Bisecting k-means and FIHC algorithms are evaluated on the performance of text clustering, and are compared with the proposed CFWS algorithm. It has been shown that CFWS has much better performance.
A new approach to intranet search based on information extraction
Authors: Hang Li, Yunbo Cao, Jun Xu, Yunhua Hu, Shenjie Li, Dmitriy Meyerzon
Venue: CIKM
Year: 2005

This paper is concerned with 'intranet search'. By intranet search, we mean searching for information on an intranet within an organization. We have found that search needs on an intranet can be categorized into types, through an analysis of survey results and an analysis of search log data. The types include searching for definitions, persons, experts, and homepages. Traditional information retrieval only focuses on search of relevant documents, but not on search of special types of information. We propose a new approach to intranet search in which we search for information in each of the special types, in addition to the traditional relevance search. Information extraction technologies can play key roles in such kind of 'search by type' approach, because we must first extract from the documents the necessary information in each type. We have developed an intranet search system called 'Information Desk'. In the system, we try to address the most important types of search first - finding term definitions, homepages of groups or topics, employees' personal information and experts on topics. For each type of search, we use information extraction technologies to extract, fuse, and summarize information in advance. The system is in operation on the intranet of Microsoft and receives accesses from about 500 employees per month. Feedbacks from users and system logs show that users consider the approach useful and the system can really help people to find information. This paper describes the architecture, features, component technologies, and evaluation results of the system.
Mining community structure of named entities from free text
Authors: Xin Li, Bing Liu
Venue: CIKM
Year: 2005

Although community discovery has been studied extensively in the Web environment, limited research has been done in the case of free text. Co-occurrence of words and entities in sentences and documents usually implies connections among them. In this paper, we investigate the co-occurrences of named entities in text, and mine communities among these entities. We show that identifying communities from free text can be transformed into a graph clustering problem. A hierarchical clustering algorithm is then proposed. Our experiment shows that the algorithm is effective to discover named entity communities from text documents.
QED: a novel quaternary encoding to completely avoid re-labeling in XML updates
Authors: Changqing Li, Tok Wang Ling
Venue: CIKM
Year: 2005

The method of assigning labels to the nodes of the XML tree is called a labeling scheme. Based on the labels only, both ordered and un-ordered queries can be processed without accessing the original XML file. One more important point for the labeling scheme is the label update cost in inserting or deleting a node into or from the XML tree. All the current labeling schemes have high update cost, therefore in this paper we propose a novel quaternary encoding approach for the labeling schemes. Based on this encoding approach, we need not re-label any existing nodes when the update is performed. Extensive experimental results on the XML datasets illustrate that our QED works much better than the existing labeling schemes on the label updates when considering either the number of nodes or the time for re-labeling.
On reducing redundancy and improving efficiency of XML labeling schemes
Authors: Changqing Li, Tok Wang Ling, Jiaheng Lu, Tian Yu
Venue: CIKM
Year: 2005

The basic relationships to be determined in XML query processing are ancestor-descendant (A-D), parent-child (P-C), sibling and ordering relationships. The containment labeling scheme can determine the A-D, P-C and ordering relationships fast, but it is very expensive in determining the sibling relationship. The prefix labeling scheme can determine all the four basic relationships fast if the XML tree is shallow. However, if the XML tree is deep, the prefix scheme is inefficient since the prefix is long. Furthermore, the prefix label is repeated by all the siblings (only the self labels of these siblings are different). Thus in this paper, we propose the P-Containment and P-Prefix schemes which can determine all the four basic relationships faster no matter what the XML structure is; meanwhile P-Prefix can reduce the redundancies in the prefix labeling scheme.
Localized routing trees for query processing in sensor networks
Authors: Jie Lian, Lei Chen, Kshirasagar Naik, M. Tamer Özsu, Gordon B. Agnew
Venue: CIKM
Year: 2005

In this paper, we propose a novel energy-efficient approach, a localized routing tree (LRT) coupled with a route redirection (RR) strategy, to support various types of queries. LRTs take care of the sensors near the sink and reduce the energy consumption of these sensors, and RR reduces the energy cost of data receptions. Compared to the existing approaches, simulation studies show that LRT together with RR has significant improvement on the query capacity.
Handling frequent updates of moving objects
Authors: Bin Lin, Jianwen Su
Venue: CIKM
Year: 2005

A critical issue in moving object databases is to develop appropriate indexing structures for continuously moving object locations so that queries can still be performed efficiently. However, such location changes typically cause a high volume of updates, which in turn poses serious problems on maintaining index structures. In this paper we propose a Lazy Group Update (LGU) algorithm for disk-based index structures of moving objects. LGU contains two key additional structures to group ``similar'' updates so that they can be performed together: a disk-based insertion buffer (I-Buffer) for each internal node, and a memory-based deletion table (D-Table) for the entire tree. Different strategies of ``pushing down'' an overflow I-Buffer to the next level are studied. Comprehensive empirical studies over uniform and skewed datasets, as well as simulated street traffic data show that LGU achieves a significant improvement on update throughput while allowing a reasonable performance for queries.
Extracting a website's content structure from its link structure
Authors: Nan Liu, Christopher C. Yang
Venue: CIKM
Year: 2005

Hierarchical models are commonly used to organize a Website's content. A Website's content structure can be represented by a topic hierarchy, a directed tree rooted at a Website's homepage in which the vertices and edges correspond to Web pages and hyperlinks. In this work, we propose an algorithm for extracting a Website's topic hierarchy from its link structure. The proposed algorithm consists of a construction stage and a refining stage, in which we analyze the semantic relationships between web pages based on link structure, web page content and directory structure. We've done extensive experiments using different Websites and obtained very promising results.
Relational computation for mining association rules from XML data
Authors: Hong-Cheu Liu, John Zeleznikow
Venue: CIKM
Year: 2005

We develop a fixpoint operator for computing large item sets and demonstrate three query paradigm solutions for association rule mining that use the idea of least fixpoint computation and indicates some optimisation issues. The results of our research provide theoretical foundation for relational computation of association rules and its application on XML mining.
Situation-aware risk management in autonomous agents
Authors: Martin Lorenz, Jan D. Gehrke, Hagen Langer, Ingo J. Timm, Joachim Hammer
Venue: CIKM
Year: 2005

We present a novel approach to enable decision-making in a highly distributed multiagent environment where individual agents need to act in an autonomous fashion. Our architecture framework integrates risk management, knowledge management, and agent deliberation to enable sophisticated, autonomous decision-making. Instead of a centralized knowledge repository, our approach supports a highly distributed knowledge base in which each agent manages a fraction of the knowledge needed by the entire system.
Applying cosine series to join size estimation
Authors: Cheng Luo, Zhewei Jiang, Wen-Chi Hou
Venue: CIKM
Year: 2005

This paper provides a general overview of two innovative applications of Cosine series in XML joins and data stream joins.
Versatile structural disambiguation for semantic-aware applications
Authors: Federica Mandreoli, Riccardo Martoglia, Enrico Ronchetti
Venue: CIKM
Year: 2005

In this paper, we propose a versatile disambiguation approach which can be used to make explicit the meaning of structure based information such as XML schemas, XML document structures, web directories, and ontologies. It can be of support to the semantic-awareness of a wide range of applications, from schema matching and query rewriting to peer data management systems, from XML data clustering to ontology-based automatic annotation of web pages and query expansion. The effectiveness of the achieved results has been experimentally proved and is founded both on a flexible exploitation of the structure context, whose extraction can be tailored on the specific application needs, and of the information provided by commonly available thesauri such as WordNet.
Improving intranet search-engines using context information from databases
Authors: Christoph Mangold, Holger Schwarz, Bernhard Mitschang
Venue: CIKM
Year: 2005

\n Information in enterprises comes in documents and databases. From a\n semantic viewpoint, both kinds of information are usually tightly\n connected. In this paper, we propose to enhance common\n search-engines with contextual information retrieved from databases.\n We establish system requirements and anecdotally demonstrate how\n documents and database information can be represented as the nodes\n of a graph. Then, we give an example how we exploit this graph\n information for document retrieval.\n
INFER: a relational query language without the complexity of SQL
Authors: Terrence Mason, Ramon Lawrence
Venue: CIKM
Year: 2005

The INFER query language allows users to express queries without referencing relations or specifying joins. Since the INFER syntax is similar to but less restrictive than SQL, users can easily write highly expressive queries that are automatically completed by INFER's inference engine. INFER's SQL-based syntax is familiar to current database users, and its improved ranking and query explanation system makes it easier to use.
Incremental evaluation of a monotone XPath fragment
Authors: Hidetaka Matsumura, Keishi Tajima
Venue: CIKM
Year: 2005

This paper shows a scheme for incremental evaluation of XPath queries. Here, we focus on a monotone fragment of XPath, i.e., when a data is deleted from (or inserted to) the database, only deletion (insertion, resp.) may occur to query answers. For efficiently processing deletions, we store information on partial matchings, i.e., which elements were participating in matchings for which query answers, and also store counters showing how many matchings each query answer had. We use the information on the partial matchings also for skipping a part of computation upon data insertion. We investigate properties of the XPath fragment in order to keep the amount of information we store as small as possible.
DIST: a distributed spatio-temporal index structure for sensor networks
Authors: Anand Meka, Ambuj K. Singh
Venue: CIKM
Year: 2005

We consider the general problem of tracking moving objects in sensor networks. The specific application we consider is that of tracking a chemical plume moving over a large infrastructure network. We present a distributed index structure DIST that stores and updates distributed summaries as the plume moves. We present algorithms for range queries on the history of the plume. DIST localizes information with respect to time and space using a hierarchy that scales with the plume size. The highlight of our work is an analytical model to predict the cost of query algorithms based on the query location, query size, and plume's spatio-temporal distribution. Using this model, our adaptive scheme chooses the optimal scheme. Experimental results show that DIST outperforms alternative techniques in query, update, and storage costs, and scales well with the number of plumes.
Context modeling and discovery using vector space bases
Authors: Massimo Melucci
Venue: CIKM
Year: 2005

In this paper, context is modeled by vector space bases and its evolution is modeled by linear transformations from one base to another. Each document or query can be associated to a distinct base, which corresponds to one context. Also, algorithms are proposed to discover contexts from document, query or groups or them. Linear algebra can thus by employed in a mathematical framework to process context, its evolution and application.
Evaluation of a MCA-based approach to organize data cubes
Authors: Riadh Ben Messaoud, Omar Boussaid, Sabine Rabaséda
Venue: CIKM
Year: 2005

In the OLAP context, exploration of huge and sparse data cubes is a tedious task that does not always lead to efficient results. We propose to use a Multiple Correspondence Analysis (MCA) in order to enhance data cube representations and make them more suitable for visualization and thus, easier to analyze. We also provide an original quality criterion to measure the relevance of the obtained data representations. Experimental results we led on real data samples have shown the interest and the efficiency of our approach.
Similarity measures for tracking information flow
Authors: Donald Metzler, Yaniv Bernstein, W. Bruce Croft, Alistair Moffat, Justin Zobel
Venue: CIKM
Year: 2005

Text similarity spans a spectrum, with broad topical similarity near one extreme and document identity at the other. Intermediate levels of similarity -- resulting from summarization, paraphrasing, copying, and stronger forms of topical relevance -- are useful for applications such as information flow analysis and question-answering tasks. In this paper, we explore mechanisms for measuring such intermediate kinds of similarity, focusing on the task of identifying where a particular piece of information originated. We consider both sentence-to-sentence and document-to-document comparison, and have incorporated these algorithms into <small>RECAP</small>, a prototype information flow analysis tool. Our experimental results with <small>RECAP</small> indicate that new mechanisms such as those we propose are likely to be more appropriate than existing methods for identifying the intermediate forms of similarity.
Document clustering using character N-grams: a comparative evaluation with term-based and word-based clustering
Authors: Yingbo Miao, Vlado Keselj, Evangelos E. Milios
Venue: CIKM
Year: 2005

We propose a novel method for document clustering using character N-grams. In the traditional vector-space model, the documents are represented as vectors, in which each dimension corresponds to a word. We propose a document representation based on the most frequent character N-grams, with window size of up to 10 characters. We derive a new distance measure, which produces uniformly better results when compared to the word-based and term-based methods. The result becomes more significant in the light of the robustness of the N-gram method with no language-dependent preprocessing. Experiments on the performance of a clustering algorithm on a variety of test document corpora demonstrate that the N-gram representation with n=3 outperforms both word and term representations. The comparison between word and term representations depends on the data set and the selected dimensionality.
Score region algebra: building a transparent XML-R database
Authors: Vojkan Mihajlovic, Henk Ernst Blok, Djoerd Hiemstra, Peter M. G. Apers
Venue: CIKM
Year: 2005

A unified database framework that will enable better comprehension of ranked XML retrieval is still a challenge in the XML database field. We propose a logical algebra, named score region algebra, that enables transparent specification of information retrieval (IR) models for XML databases. The transparency is achieved by a possibility to instantiate various retrieval models, using abstract score functions within algebra operators, while logical query plan and operator definitions remain unchanged. Our algebra operators model three important aspects of XML retrieval: element relevance score computation, element score propagation, and element score combination. To illustrate the usefulness of our algebra we instantiate four different, well known IR scoring models, and combine them with different score propagation and combination functions. We implemented the algebra operators in a prototype system on top of a low-level database kernel. The evaluation of the system is performed on a collection of IEEE articles in XML format provided by INEX. We argue that state of the art XML IR models can be transparently implemented using our score region algebra framework on top of any low-level physical database engine or existing RDBMS, allowing a more systematic investigation of retrieval model behavior.
Access control for XML: a dynamic query rewriting approach
Authors: Sriram Mohan, Arijit Sengupta, Yuqing Wu
Venue: CIKM
Year: 2005

Being able to express and enforce role-based access control on XML data is a critical component of XML data management. However, given the semi-structured nature of XML, this is non-trivial, as access control can be applied on the values of nodes as well as on the structural relationship between nodes. In this context, we adopt and extend a graph editing language for specifying role-based access constraints in the form of security views. A Security Annotated Schema (SAS) is proposed as the internal representation for the security views and can be automatically constructed from the original schema and the security view specification. To enforce the access constraints on user queries, we propose Secure Query Rewrite (SQR) -- a set of rules that can be used to rewrite a user XPath query on the security view into an equivalent XQuery expression against the original data, with the guarantee that the users only see information in the view but not any data that was blocked. Experimental evaluation demonstrates the efficiency and the expressiveness of our approach.
Efficient evaluation of parameterized pattern queries
Authors: Cédric du Mouza, Philippe Rigaux, Michel Scholl
Venue: CIKM
Year: 2005

Many applications rely on sequence databases and use extensively pattern-matching queries to retrieve data of interest. This paper extends the traditional pattern-matching expressions to parameterized patterns, featuring variables. Parameterized patterns are more expressive and allow to define concisely regular expressions that would be very complex to describe without variables. They can also be used to express additional constraints on patterns' variables.We show that they can be evaluated without additional cost with respect to traditional techniques (e.g., the Knuth-Morris-Pratt algorithm). We describe an algorithm that enjoys low memory and CPU time requirements, and provide experimental results which illustrate the gain of the optimized solution.