OpenRaiser/Intern-Atlas huggingface dataset:
Scalable summary based retrieval in P2P networks
Authors: Wolfgang Müller, Martin Eisenhardt, Andreas Henrich
Venue: CIKM
Year: 2005

Much of the present P2P-IR literature is focused on distributed indexing structures. Within this paper, we present an approach based on the replication of peer data summaries via rumor spreading and multicast in a structured overlay.We will describe Rumorama, a P2P framework for similar-ity queries inspired by GlOSS and CORI and their P2P-adaptation, PlanetP. Rumorama achieves a hierarchization of PlanetP-like summary-based P2P-IR networks. In a Rumorama network, each peer views the network as a small PlanetP network with connections to peers that see other small PlanetP networks. One important aspect is that each peer can choose the size of the PlanetP network it wants to see according to its local processing power and bandwidth. Even in this adaptive environment, Rumorama manages to process a query such that the summary of each peer is considered exactly once in a network without churn. However, the actual number of peers to be contacted for a query is a small fraction of the total number of peers in the network.Within this article, we present the Rumorama base protocol, as well as experiments demonstrating the scalability and viability of the approach under churn.
DSAC: integrity for outsourced databases with signature aggregation and chaining
Authors: Maithili Narasimha, Gene Tsudik
Venue: CIKM
Year: 2005

Database outsourcing is an important trend which involves data owners farming out their data management needs to an external service provider. One important requirement is to maintain the integrity and authenticity of outsourced data. Whenever an outsourced database is queried, the corresponding query reply must be demonstrably authentic. Furthermore, a reply must include a proof of completeness to convince the querier that no data matching the query predicate(s) has been omitted. In this paper, we suggest new techniques in support of efficient authenticity and completeness guarantees of such query replies.
Clustering high-dimensional data using an efficient and effective data space reduction
Authors: Ratko Orlandic, Ying Lai, Wai Gen Yee
Venue: CIKM
Year: 2005

This paper introduces a new algorithm for clustering data in high-dimensional feature spaces, called GARDENHD. The algorithm is organized around the notion of data space reduction, i.e. the process of detecting dense areas (dense cells) in the space. It performs effective and efficient elimination of empty areas that characterize typical high-dimensional spaces and an efficient adjacency-connected agglomeration of dense cells into larger clusters. It produces a compact representation that can effectively capture the essence of data. GARDENHD is a hybrid of cell-based and density-based clustering. However, unlike typical clustering methods in its class, it applies a recursive partition of sparse regions in the space using a new space-partitioning strategy. The properties of this partitioning strategy greatly facilitate data space reduction. The experiments on synthetic and real data sets reveal that GARDENHD and its data space reduction are effective, efficient, and scalable.
Selectivity-based partitioning: a divide-and-union paradigm for effective query optimization
Authors: Neoklis Polyzotis
Venue: CIKM
Year: 2005

Modern query optimizers select an efficient join ordering for a physical execution plan based essentially on the average join selectivity factors among the referenced tables. In this paper, we argue that this "monolithic" approach can miss important opportunities for the effective optimization of relational queries. We propose selectivity-based partitioning, a novel optimization paradigm that takes into account the join correlations among relation fragments in order to essentially enable multiple (and more effective) join orders for the evaluation of a single query. In a nutshell, the basic idea is to carefully partition a relation according to the selectivities of the join operations, and subsequently rewrite the query as a union of constituent queries over the computed partitions. We provide a formal definition of the related optimization problem and derive properties that characterize the set of optimal solutions. Based on our analysis, we develop a heuristic algorithm for computing efficiently an effective partitioning of the input query. Results from a preliminary experimental study verify the effectiveness of the proposed approach and demonstrate its potential as an effective optimization technique.
Maximal termsets as a query structuring mechanism
Authors: Bruno Pôssas, Nivio Ziviani, Berthier A. Ribeiro-Neto, Wagner Meira Jr.
Venue: CIKM
Year: 2005

Search engines process queries conjunctively to restrict the size of the answer set. Further, it is not rare to observe a mismatch between the vocabulary used in the text of Web pages and the terms used to compose the Web queries. The combination of these two features might lead to irrelevant query results, particularly in the case of more specific queries composed of three or more terms. To deal with this problem we propose a new technique for automatically structuring Web queries as a set of smaller subqueries. To select representative subqueries we use information on their distributions in the document collection. This can be adequately modeled using the concept of maximal termsets derived from the formalism of association rules theory. Experimentation shows that our technique leads to improved results. For the TREC-8 test collection, for instance, our technique led to gains in average precision of roughly 28% with regard to a BM25 ranking formula.
Efficient indexing and querying of XML data using modified Prüfer sequences
Authors: K. Hima Prasad, P. Sreenivasa Kumar
Venue: CIKM
Year: 2005

With the advent of XML as the new standard for information representation and exchange, indexing and querying of XML data is of major concern. In this paper, we propose a method for representing an XML document as a sequence based on a variation of Prüfer sequences. We incorporate new components in the node encodings such as level, number of a certain kind of descendants and develop methods for holistic processing of tree pattern queries. The query processing involves converting the query also into a sequence and performing subsequence matching on the document sequence. We establish certain interesting properties of the proposed method of sequencing that give rise to a new efficient pattern matching algorithm. The sequence data is stored in a two level B+-trees to support query processing. We also propose an optimization for parent-child axis to speed up the query processing. Our approach does not require any post-processing and guarantees results that are free of false positives and duplicates. Experimental results show that our system performs significantly better than previous systems in a large number of cases.
Typed functional query languages with equational specifications
Authors: Ken Q. Pu, Alberto O. Mendelzon
Venue: CIKM
Year: 2005

We present a framework for functionally modeling query languages and data models. Data and queries are uniformly represented by first-order functions, and query-language constructs by polymorphic higher-order functions. The functions are typed by a database-oriented type system that supports polymorphism and nesting of types, thus one can perform static type-checking and type-inferencing of query-expressions. The query language can be freely extended by introducing new querying constructs as polymorphic higher-order functions.While type information gives the input-output description of the functions, the semantic information is captured by equational specifications. Knowledge about the functions is represented as equalities of functional expressions in the form of equations. By equational axiomatization of the query language, database problems of query equivalence and answering-query with views can be posed as equational word-problems and equational matching.
A structure-sensitive framework for text categorization
Authors: Ganesh Ramakrishnan, Deepa Paranjpe, Byron Dom
Venue: CIKM
Year: 2005

This paper presents a framework called Structure Sensitive CATegorization(SSCAT), that exploits document structure for improved categorization. There are two parts to this framework, viz. (1) Documents often have layout structure, such that logically coherent text is grouped together into fields using some mark-up language. We use a log-linear model, which associates one or more features with each field. Weights associated with the field features are learnt from training data and these weights quantify the per-class importance of the field features in determining the category for the document. (2) We employ a technique that exploits the parse tree of fields that are phrasal constructs, such as title and associates weights with words in these constructs while boosting weights of important words called focus words. These weights are learnt from example instances of phrasal constructs, marked with the corresponding focus words. The learning is accomplished by training a classifier that uses linguistic features obtained from the text's parse structure. The weighted words, in fields with phrasal constructs, are used in obtaining features for the corresponding fields in the overall framework. SSCAT was tested on the supervised categorization task of over one million products from Yahoo!'s on-line shopping data. With an accuracy of over 90%, our classifier outperforms Naive Bayes and Support Vector Machines. This not only shows the effectiveness of SSCAT but also strengthens our belief that linguistic features based on natural language structure can improve tasks such as text categorization.
Semantic verification for fact seeking engines
Authors: Dmitri Roussinov, Weiguo Fan, Fernando Adrian Das Neves
Venue: CIKM
Year: 2005

We present the architecture of our web question answering (fact seeking) system and introduce a novel algorithm to validate semantic categories of the expected answers. When tested on the questions used by the prior research, our system demonstrated the performance comparable to the current state of the art systems. Our semantic verification algorithm has improved the accuracy of answers of the affected questions by 30%.
Discretization based learning approach to information retrieval
Authors: Dmitri Roussinov, Weiguo Fan, Fernando Adrian Das Neves
Venue: CIKM
Year: 2005

We have designed a representation scheme, which is based on the discrete representation of a document ranking function, which is capable of reproducing and enhancing the properties of such popular ranking functions as tf.idf, BM25 or those based on language models. Our tests have demonstrated the capability of our approach to achieve the performance of the best known scoring functions solely through training, without using any known heuristic or analytic formulas.
Towards automatic association of relevant unstructured content with structured query results
Authors: Prasan Roy, Mukesh K. Mohania, Bhuvan Bamba, Shree Raman
Venue: CIKM
Year: 2005

Faced with growing knowledge management needs, enterprises are increasingly realizing the importance of seamlessly integrating critical business information distributed across both structured and unstructured data sources. In existing information integration solutions, the application needs to formulate the SQL logic to retrieve the needed structured data on one hand, and identify a set of keywords to retrieve the related unstructured data on the other. This paper proposes a novel approach wherein the application specifies its information needs using only a SQL query on the structured data, and this query is automatically ``translated'' into a set of keywords that can be used to retrieve relevant unstructured data. We describe the techniques used for obtaining these keywords from (i) the query result, and (ii) additional related information in the underlying database. We further show that these techniques achieve high accuracy with very reasonable overheads.
A robot ontology for urban search and rescue
Authors: Craig Schlenoff, Elena Messina
Venue: CIKM
Year: 2005

The goal of this Robot Ontology effort is to develop and begin to populate a neutral knowledge representation (the data structures) capturing relevant information about robots and their capabilities to assist in the development, testing, and certification of effective technologies for sensing, mobility, navigation, planning, integration and operator interaction within search and rescue robot systems. This knowledge representation must be flexible enough to adapt as the robot requirements evolve. As such, we have chosen to use an ontological approach to representing these requirements. This paper describes the Robot Ontology, how it fits in to the overall Urban Search and Rescue effort, how we will be proceeding in the future.
self awareness in the mobility open architecture simulation and tools framework
Authors: Chris Scrapper, Stephen Balakirsky, Elena Messina
Venue: CIKM
Year: 2005

A Multi-Agent System's (MAS) overall performance is tightly coupled to the system's ability to schedule, monitor, and coordinate activities. These activities must maximize each individual agent"s utility to the group while minimizing the duration of the overall mission. The efficient acquisition and conveying of knowledge is critical to these activities. This paper describes the integration of meta-level knowledge and techniques for knowledge acquisition and conveyance in the Mobility Open Architecture Simulation and Tools (MOAST) framework. These knowledge systems enhance the simulation environment and provide the ability to develop, test, and analyze agents.
Leonardo's laptop: human needs and the new computing technologies
Authors: Ben Shneiderman
Venue: CIKM
Year: 2005

The old computing was about what computers could do; the new computing is about what people can do.To accelerate the shift from the old to the new computing designers need to:
ViPER: augmenting automatic information extraction with visual perceptions
Authors: Kai Simon, Georg Lausen
Venue: CIKM
Year: 2005

In this paper we address the problem of unsupervised Web data extraction. We show that unsupervised Web data extraction becomes feasible when supposing pages that are made up of repetitive patterns, as it is the case, e.g., for search engine result pages. Hereby the extraction rules are generated automatically without any training or human interaction, by means of operating on the DOM tree respectively the flat tag token sequence of a single page.Our contribution to automatic data extraction through this paper is twofold. First, we identify and rank potential repetitive patterns with respect to the user's visual perception of the Web page, well aware that location and size of matching elements within a Web page constitute important criteria for defining relevance. Second, matching sub-sequences of the pattern with the highest weightiness are aligned with global multiple sequence alignment techniques. Experimental results show that our system is able to achieve high accuracy in distilling and aligning regularly structured objects inside complex Web pages.
Automated cleansing for spend analytics
Authors: Moninder Singh, Jayant Kalagnanam, Sudhir Verma, Amit J. Shah, Swaroop K. Chalasani
Venue: CIKM
Year: 2005

The development of an aggregate view of the procurement spend across an enterprise using transactional data is increasingly becoming a very important and strategic activity. Not only does it provide a complete and accurate picture of what the enterprise is buying and from whom, it also allows it to consolidate suppliers, as well as negotiate better prices. The importance, as well as the complexity, of this cleansing exercise is further magnified by the increasing popularity of Business Transformation Outsourcing (BTO) wherein enterprises are turning over non-core activities, such as indirect procurement, to third parties, who now need to develop an integrated view of spend across multiple enterprises in order to optimize procurement and generate maximum savings. However, the creation of such an integrated view of procurement spend requires the creation of a homogeneous data repository from disparate (heterogeneous) data sources across various geographic and functional organizations throughout the enterprise(s). Such repositories get transactional data from various sources such as invoices, purchase orders, account ledgers. As such, the transactions are not cross-indexed, refer to the same suppliers by different names, and use different ways of representing information about the same commodities. Before an aggregated spend view can be developed, this data needs to be cleansed, primarily to normalize the supplier names and correctly map each transaction to the appropriate commodity code. Commodity mapping, in particular, is made more difficult by the fact that it has to be done on the basis of unstructured text descriptions found in the various data sources. We describe an on-demand system to automatically perform this cleansing activity using techniques from information retrieval and machine learning. Built on standard integration and application infrastructure software, this system provides enterprises with a fast, reliable, accurate and on-demand way of cleansing transactional data and generating an integrated view of spend. This system is currently in the process of being deployed by IBM for use in its BTO practice.
Unapparent information revelation: a concept chain graph approach
Authors: Rohini K. Srihari, Sudarshan Lamkhede, Anmol Bhasin
Venue: CIKM
Year: 2005

Information generated by multiple authors working independently at different times when analyzed synergistically reveals more information than apparent. For example, a traditional search for connections between the trucking industry and Iraqi banks may not produce any documents mentioning both. However, a search that follows trails of associations across documents may suggest a connection between an auto parts manufacturer who exports to Iraq, and an Iraqi bank providing loans to buy cars. The work described here extends link analysis based on named entities and labeled relationships to general concepts and unnamed associations. Unapparent Information Revelation involves finding chains connecting concepts across documents: it uses a new representation formalism called Concept Chain Graphs.
D-CAPE: distributed and self-tuned continuous query processing
Authors: Timothy M. Sutherland, Bin Liu, Mariana Jbantova, Elke A. Rundensteiner
Venue: CIKM
Year: 2005

Efficient continuous query processing is critical for many applications, including monitoring remote sensors network traffic management, and online transaction processing. To overcome resource limitations and achieve real-time responsiveness, continuous query systems research focuses on issues such as punctuation-driven operator-state purging [4], load shedding, operator scheduling [7] and plan optimization and on-line migration [9]. However, when real-time yet accurate results are critical such as in stock market analysis, then there is a limitation to what any of the above optimization techniques can accomplish. Hence, distributed processing must be applied to support required scalability. It has been already proven in traditional database systems [3] that distributed processing results in high scale-up and speed-up capabilities due to aggregated resources. The design of a distributed continuous query system is characterized by an extra complexity, considered in the design of our D-Cape engine. In such a system, data streams may be infinite and initial cost statistics about the data streams are typically unknown. Moreover, cost statistics continue to change over time. Our research on distributed stream processing addresses two critical questions: (1) How to initially distribute query plans given little or possibly no cost information, and (2) How to efficiently adapt the query distribution corresponding to runtime environmental changes. Even though research is now under way in designing distributed continuous query systems [2], [1], results to date, as far as we know, are based on simulations. Our work offers empirical results of distributed continuous query processing using an actual software system [5], [6]. D-Cape, a distributed continuous query processing architecture, employs stream query engines over a cluster of shared-nothing processors. We employ a dedicated distribution manager to manage
A novel refinement approach for text categorization
Authors: Songbo Tan, Xueqi Cheng, Moustafa Ghanem, Bin Wang, Hongbo Xu
Venue: CIKM
Year: 2005

In this paper we present a novel strategy, DragPushing, for improving the performance of text classifiers. The strategy is generic and takes advantage of training errors to successively refine the classification model of a base classifier. We describe how it is applied to generate two new classification algorithms; a Refined Centroid Classifier and a Refined Naïve Bayes Classifier. We present an extensive experimental evaluation of both algorithms on three English collections and one Chinese corpus. The results indicate that in each case, the refined classifiers achieve significant performance improvement over the base classifiers used. Furthermore, the performance of the Refined Centroid Classifier implemented is comparable, if not better, to that of state-of-the-art support vector machine (SVM)-based classifier, but offers a much lower computational cost.
Balancing performance and confidentiality in air index
Authors: Qingzhao Tan, Wang-Chien Lee, Baihua Zheng, Peng Liu, Dik Lun Lee
Venue: CIKM
Year: 2005

Studies on the performance issues (i.e., access latency and energy conservation) of wireless data broadcast have appeared in the literature. However, the important security issues have not been well addressed. This paper investigates the tradeoff between performance and security of signature-based air index schemes in wireless data broadcast. From the performance perspective, keeping low false drop probability helps clients retrieve the information from a broadcast channel efficiently. Meanwhile, from the security perspective, achieving high false guess probability prevents the hacker from guessing the information easily. There is a tradeoff between these two aspects. An administrator of the wireless broadcast system may balance this tradeoff by carefully configuring the signatures used in broadcast. This study provides a guidance for parameter settings of the signature schemes in order to meet the performance and security requirements. Experiments are performed to validate the analytical results and to obtain optimal signature configuration corresponding to different application criteria.