OpenRaiser/Intern-Atlas huggingface dataset:
Approximating the top-m passages in a parallel question answering system
Authors: Charles L. A. Clarke, Egidio L. Terra
Venue: CIKM
Year: 2004

We examine the problem of retrieving the top-<i>m</i> ranked items from a large collection, randomly distributed across an <i>n</i>-node system. In order to retrieve the top <i>m</i> overall, we must retrieve the top <i>m</i> from the subcollection stored on each node and merge the results. However, if we are willing to accept a small probability that one or more of the top-<i>m</i> items may be missed, it is possible to reduce computation time by retrieving only the top <i>k < m</i> from each node. In this paper, we demonstrate that this simple observation can be exploited in a realistic application to produce a substantial efficiency improvement without compromising the quality of the retrieved results. To support our claim, we present a statistical model that predicts the impact of the optimization. The paper is structured around a specific application~---~passage retrieval for question answering~---~but the primary results are more broadly applicable.
Database support for species extraction from the biosystematics literature: a feasibility demonstration
Authors: Ralf Duckstein, Klemens Böhm
Venue: CIKM
Year: 2004

A part of the biosystematics literature is currently being digitized and manually marked up with XML. Fast search on such documents shall be feasible. But marking up such documents incurs high costs, and biologists would like to know the value of such an activity in advance. Deploying standard XML database technology in a straightforward way is not feasible, because of two characteristics of biosystematics documents. The first one is that descriptions of taxa are related, i.e., a more specific taxon should inherit from a more general one. The combination of inheritance with information-retrieval mechanisms gives rise to difficulties addressed in this article. The second issue is the frequent occurrence of very specific technical terms in such documents, i.e., geographical information or biological terms. To investigate the characteristics of the search in the presence of such difficulties, we have designed and implemented a respective system, based on relational database technology. We use a collection of XML documents that mimics the characteristics of biosystematics documents, as we will explain. We propose two query-evaluation alternatives and compare them by means of performance experiments. It turns out that our techniques can administer the envisioned corpus of documents efficiently and cope with those problems at the same time.
The liberal media and right-wing conspiracies: using cocitation information to estimate political orientation in web documents
Authors: Miles Efron
Venue: CIKM
Year: 2004

This paper introduces a simple method for estimating cultural orientation, the affiliation of online entities in a polarized field of discourse. In particular, cocitation information is used to estimate the political orientation of hypertext documents. A type of cultural orientation, the political orientation of a document is the degree to which it participates in traditionally left- or right-wing beliefs. Estimating documents' political orientation is of interest for personalized information retrieval and recommender systems. In its application to politics, the method uses a simple probabilistic model to estimate the strength of association between a document and left- and right-wing communities. The model estimates the likelihood of cocitation between a document of interest and a small number of documents of known orientation. The model is tested on three sets of data, 695 partisan web documents, 162 political weblogs, and 72 non-partisan documents. Accuracy above 90% is obtained from the cocitation model, outperforming lexically based classifiers at statistically significant levels.
A design space approach to analysis of information retrieval adaptive filtering systems
Authors: Dmitriy Fradkin, Paul B. Kantor
Venue: CIKM
Year: 2004

In this paper we suggest a new approach to analysis and design of IR systems. We argue for design space exploration in constructing IR systems and in analyzing the effects of individual modules and parameters. We present results of experiments with parametric interpolation, or "homotopy", between two systems, and show, incidentally, that the best results are not achieved at the endpoints, and may lie outside the bounding hypercube defined by our choice of parameterization. Three distinct classes of interpolation are introduced to deal with the complexities of the specific example.
Motion adaptive indexing for moving continual queries over moving objects
Authors: Bugra Gedik, Kun-Lung Wu, Philip S. Yu, Ling Liu
Venue: CIKM
Year: 2004

This paper describes a <i>motion adaptive</i> indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of <i>motion-sensitive bounding boxes</i> (<i>MSB</i>s) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query <i>MSB</i>s, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use <i>predictive query results</i> to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Our experiments show that the proposed motion adaptive indexing scheme is efficient for the evaluation of moving continual range queries.
Framework and algorithms for trend analysis in massive temporal data sets
Authors: Sreenivas Gollapudi, D. Sivakumar
Venue: CIKM
Year: 2004

Mining massive temporal data streams for significant trends, emerging buzz, and unusually high or low activity is an important problem with several commercial applications. In this paper, we propose a framework based on relational records and metric spaces to study such problems. Our framework provides the necessary mathematical underpinnings for this genre of problems, and leads to efficient algorithms in the stream/sort model of massive data sets (where the algorithm makes passes over the data, computes a new stream on the fly, and is allowed to sort the intermediate data). Our algorithm makes novel use of metric approximations in the data stream context, and highlights the role of hierarchical organization of large data sets in designing efficient algorithms in the stream/sort model.
The semantic web: managing knowledge for planet earth
Authors: Patrick J. Hayes
Venue: CIKM
Year: 2004

The Semantic Web (SWeb) is a vision - actually, a number of visions - which is beginning to show some signs of potential reality. The core of the vision is a synergy between machine-accessible knowledge and the global reach of the Web. The deployment of knowledge technologies on a planet-wide open network brings new challenges and opportunities, many of them not yet fully realized. This talk briefly surveys the current state of play in SWeb standards and technology, including some of the rather heated controversies, and tries to give a high-level view of some of these challenges and opportunities. Some traditional hard problems in KM may largely evaporate; but new ones will take their place.
Organizing structured web sources by query schemas: a clustering approach
Authors: Bin He, Tao Tao, Kevin Chen-Chuan Chang
Venue: CIKM
Year: 2004

In the recent years, the Web has been rapidly "deepened" with the prevalence of databases online. On this deep Web, many sources are <i>structured</i> by providing structured query interfaces and results. Organizing such structured sources into a domain hierarchy is one of the critical steps toward the integration of heterogeneous Web sources. We observe that, for structured Web sources, query schemas <i>ie</i>, attributes in query interfaces) are discriminative representatives of the sources and thus can be exploited for source characterization. In particular, by viewing query schemas as a type of categorical data, we abstract the problem of source organization into the clustering of categorical data. Our approach hypothesizes that "homogeneous sources" are characterized by the same hidden generative models for their schemas. To find clusters governed by such statistical distributions, we propose a new objective function, <i>model-differentiation</i>, which employs principled hypothesis testing to maximize statistical heterogeneity among clusters. Our evaluation over hundreds of real sources indicates that (1) the schema-based clustering accurately organizes sources by object domains <i>eg</i>, Books, Movies), and (2) on clustering Web query schemas, the model-differentiation function outperforms existing ones, such as likelihood, entropy, and context linkages, with the hierarchical agglomerative clustering algorithm.
Indexing text data under space constraints
Authors: Bijit Hore, Hakan Hacigümüs, Balakrishna R. Iyer, Sharad Mehrotra
Venue: CIKM
Year: 2004

An important class of queries is the LIKE predicate in SQL. In the absence of an index, LIKE queries are subject to performance degradation. The notion of indexing on substrings (or <i>q</i>-grams) has been explored earlier without sufficient consideration of efficiency. <i>q</i>-grams are used to prune away rows that do not qualify for the query. The problem is to identify a finite number of grams subject to storage constraint that gives maximal pruning for a given query workload. Our contributions include: i) a formal problem definition, that produces results within a provable error bound, ii) performance evaluation of the application of the novel method to real data, and iii) parallelization of the algorithm, scaling considerations and a proposal to handle scaling issues.
Compression schemes for differential categorical stream clustering
Authors: Weiyun Huang, Edward Omiecinski, Leo Mark
Venue: CIKM
Year: 2004

Stream data analysis differs significantly from traditional data processing. To process the data online the algorithm has to work in one pass, incorporating new data into a model maintained in main memory. Storing a model or synopsis of processed data in the memory, which we call "data compression", is an important technique in both incremental and differential stream mining. This paper proposes several data compression schemes in one-pass categorical data clustering, and demonstrates their performance on synthetic and real data. Our compression schemes can efficiently generate compact representations of original data, so as to enable the algorithm to process streams at high speed and detect the changes in underlying data. The example algorithm based on these compression schemes achieves good accuracy in short execution time.
Localized signature table: fast similarity search on transaction data
Authors: Qiang Jing, Rui Yang, Panos Kalnis, Anthony K. H. Tung
Venue: CIKM
Year: 2004

Recently, techniques for supporting efficient similarity search over huge transaction datasets have emerged as an important research area. Several indexing schemes have been proposed towards this direction. Typically, these schemes provide a tradeoff between searching efficiency and indexing overhead in terms of space. In this paper, we propose a novel indexing scheme for similarity search on transaction data. Based on well-studied clustering techniques, we develop a construction algorithm for the proposed index and a branch-and-bound searching strategy for answering similarity search. Unlike previous techniques, our indexing scheme exhibits high search efficiency and low space requirements by trading-off the pre-computation time. This behavior is ideal for applications with low update but high read volume <i>e.g.</i>, data warehousing, collaborative filtering, <i>etc.</i>). Moreover, our experimental results illustrate that our method is robust to the varying characteristics of the datasets.
SERF: integrating human recommendations with search
Authors: Seikyung Jung, Kevin Harris, Janet Webster, Jonathan L. Herlocker
Venue: CIKM
Year: 2004

Today's university library has many digitally accessible resources, both indexes to content and considerable original content. Using off-the-shelf search technology provides a single point of access into library resources, but we have found that such full-text indexing technology is not entirely satisfactory for library searching.
Processing search queries in a distributed environment
Authors: Frederick Knabe, Daniel Tunkelang
Venue: CIKM
Year: 2004

Endeca's approach to processing search queries in a distributed computing environment is predicated on concerns of correctness, scalability, and flexibility in deployment. Using a master-slave architecture, we are able to support classic search as well as more advanced features. We avoid bottlenecking the master with excessive computation or communication by limiting the information from the slaves in the expected case.
Stemming and lemmatization in the clustering of finnish text documents
Authors: Tuomo Korenius, Jorma Laurikkala, Kalervo Järvelin, Martti Juhola
Venue: CIKM
Year: 2004

Stemming and lemmatization were compared in the clustering of Finnish text documents. Since Finnish is a highly inflectional and agglutinative language, we hypothesized that lemmatization, involving splitting of the compound words, would be more appropriate normalization approach than the straightforward stemming. The relevance of the documents were evaluated with a four-point relevance assessment scale, which was collapsed into binary one by considering all the relevant and only the highly relevant documents relevant, respectively. Experiments with four hierarchical clustering methods supported the hypothesis. The stringent relevance scale showed that lemmatization allowed the single and complete linkage methods to recover especially the highly relevant documents better than stemming. In comparison with stemming, lemmatization together with the average linkage and Ward's methods produced higher precision. We conclude that lemmatization is a better word normalization method than stemming, when Finnish text documents are clustered for information retrieval.
Towards smarter documents
Authors: Vikas Krishna, Prasad M. Deshpande, Savitha Srinivasan
Venue: CIKM
Year: 2004

Document analysis research typically focuses on document image understanding or classic problems in text classification, clustering, summarization and discovery. While that is an important aspect of document management, in practice, documents lifecycles are often determined by the context of the business process that they are relevant to. It therefore becomes necessary for the document analysis techniques to recognize and leverage the contextual information provided by a supporting schema and business process. This paper presents an intelligent document management framework with relevant document analysis, metadata extraction, and business process association algorithms and methodology. The architecture supporting this framework seamlessly integrates a runtime environment with an authoring environment by combining relational data modeling tools with document classification techniques. The runtime environment accepts incoming documents, classifies the document, extracts metadata and executes customized business logic. The authoring environment supports the association of a class of documents with a relational document schema, identification of attribute values that must be extracted automatically, generation of relevant business logic, and deployment of authoring artifacts into the runtime architecture. We demonstrate the use of this framework with representative real-world document transformative applications.
Distributional term representations: an experimental comparison
Authors: Alberto Lavelli, Fabrizio Sebastiani, Roberto Zanoli
Venue: CIKM
Year: 2004

A number of content management tasks, including term categorization, term clustering, and automated thesaurus generation, view natural language (e.g. words, noun phrases) as first-class objects, i.e. as objects endowed with an internal representation which makes them suitable for explicit manipulation by the corresponding algorithms. The information retrieval (IR) literature has traditionally used an extensional (aka distributional) representation for according to which a term is represented by the bag of documents in which the term occurs. The computational linguistics (CL) literature has independently developed an alternative distributional representation for terms, according to which a term is represented by the bag of terms that co-occur with it in some document. This paper aims at discovering which of the two representations is most effective, i.e. brings about higher effectiveness once used in tasks that require to be explicitly represented and manipulated. We carry out experiments on (i) a term categorization task, and (ii) a term clustering task; this allows us to compare the two different representations in closely controlled experimental conditions. We report the results of experiments in which we categorize/cluster under 42 different classes the extracted from a corpus of more than 65,000 documents. Our results show a substantial difference in effectiveness between the two representation styles; we give both an intuitive explanation and an information-theoretic justification for these different behaviours.
On combining multiple clusterings
Authors: Tao Li, Mitsunori Ogihara, Sheng Ma
Venue: CIKM
Year: 2004

Many problems can be reduced to the problem of combining multiple clusterings. In this paper, we first summarize different application scenarios of combining multiple clusterings and provide a new perspective of viewing the problem as a categorical clustering problem. We then show the connections between various consensus and clustering criteria and discuss the complexity results of the problem. Finally we propose a new method to determine the final clustering. Experiments on kinship terms and clustering popular music from heterogeneous feature sets show the effectiveness of combining multiple clusterings.
Learning similarity measures in non-orthogonal space
Authors: Ning Liu, Benyu Zhang, Jun Yan, Qiang Yang, Shuicheng Yan, Zheng Chen, Fengshan Bai, Wei-Ying Ma
Venue: CIKM
Year: 2004

Many machine learning and data mining algorithms crucially rely on the similarity metrics. The Cosine similarity, which calculates the inner product of two normalized feature vectors, is one of the most commonly used similarity measures. However, in many practical tasks such as text categorization and document clustering, the Cosine similarity is calculated under the assumption that the input space is an orthogonal space which usually could not be satisfied due to synonymy and polysemy. Various algorithms such as Latent Semantic Indexing (LSI) were used to solve this problem by projecting the original data into an orthogonal space. However LSI also suffered from the high computational cost and data sparseness. These shortcomings led to increases in computation time and storage requirements for large scale realistic data. In this paper, we propose a novel and effective similarity
Efficient processing of XML twig patterns with parent child edges: a look-ahead approach
Authors: Jiaheng Lu, Ting Chen, Tok Wang Ling
Venue: CIKM
Year: 2004

With the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an XML database. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms are quite efficient for quires with only ancestor-descendant edges. But for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. To overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely <i>TwigStackList</i>. Our main technique is to look-ahead read some elements in input data steams and cache limited number of them to <i>lists</i> in the main memory. The number of elements in any list is bounded by the length of the longest path in the XML document. We show that <i>TwigStackList</i> is I/O optimal for queries with only ancestor-descendant relationships below branching nodes. Further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in <i>TwigStackList</i> is guaranteed to be a subset of that in previous algorithms. We complement our experimental results on a range of real and synthetic data to show the significant superiority of <i>TwigStackList</i> over previous algorithms for queries with <i>parent</i>-<i>child</i> relationships.
QFilter: fine-grained run-time XML access control via NFA-based query rewriting
Authors: Bo Luo, Dongwon Lee, Wang-Chien Lee, Peng Liu
Venue: CIKM
Year: 2004

At present, most of the state-of-the-art solutions for XML access controls are either (1) document-level access control techniques that are too limited to support fine-grained security enforcement; (2) view-based approaches that are often expensive to create and maintain; or (3) impractical proposals that require substantial security-related support from underlying XML databases. In this paper, we take a different approach that assumes no security support from underlying XML databases and examine three alternative fine-grained XML access control solutions, namely <i>primitive, pre-processing</i> and <i>post-processing</i> approaches. In particular, we advocate a pre-processing method called <i>QFilter</i> that uses Non-deterministic Finite Automata (NFA) to rewrite user's query such that any parts violating access control rules are pruned. We show the construction and execution of a QFilter and demonstrate its superiority to other competing methods.
A multi-system analysis of document and term selection for blind feedback
Authors: Thomas R. Lynam, Chris Buckley, Charles L. A. Clarke, Gordon V. Cormack
Venue: CIKM
Year: 2004

Experiments were conducted to explore the impact of combining various components of eight leading information retrieval systems. Each system demonstrated improved effectiveness with the use of <i>blind feedback</i>, in which the results of a preliminary retrieval step were used to augment the efficacy of a secondary retrieval step. The hybrid combination of primary and secondary retrieval steps from different systems in a number of cases yielded better effectiveness than either of the constituent systems alone. This positive combining effect was observed when entire documents were passed between the two retrieval steps, but not when only the expansion terms were passed. Several combinations of primary and secondary retrieval steps were fused using the CombMNZ algorithm; all yielded significant effectiveness improvement over the individual systems, with the best yielding a an improvement of 13% (<i>p</i> = 10<sup>-6</sup>) over the best individual system and an improvement of 4% (<i>p</i> = 10<sup>-5</sup>) over a simple fusion of the eight systems.