OpenRaiser/Intern-Atlas huggingface dataset:
KDDCS: a load-balanced in-network data-centric storage scheme for sensor networks
Authors: Mohamed Aly, Kirk Pruhs, Panos K. Chrysanthis
Venue: CIKM
Year: 2006

We propose an In-Network Data-Centric Storage (INDCS) scheme for answering ad-hoc queries in sensor networks. Previously proposed In-Network Storage (INS) schemes suffered from Storage Hot-Spots that are formed if either the sensors' locations are not uniformly distributed over the coverage area, or the distribution of sensor readings is not uniform over the range of possible reading values. Our K-D tree based Data-Centric Storage (KDDCS) scheme maintains the invariant that the storage of events is distributed reasonably uniformly among the sensors. KDDCS is composed of a set of distributed algorithms whose running time is within a poly-log factor of the diameter of the network. The number of messages any sensor has to send, as well as the bits in those messages, is poly-logarithmic in the number of sensors. Load balancing in KDDCS is based on defining and distributively solving a theoretical problem that we call the Weighted Split Median problem. In addition to analytical bounds on KDDCS individual algorithms, we provide experimental evidence of our scheme's general efficiency, as well as its ability to avoid the formation of storage hot-spots of various sizes, unlike all previous INDCS schemes.
Effective and efficient classification on a search-engine model
Authors: Aris Anagnostopoulos, Andrei Z. Broder, Kunal Punera
Venue: CIKM
Year: 2006

Traditional document classification frameworks, which apply the learned classifier to each document in a corpus one by one, are infeasible for extremely large document corpora, like the Web or large corporate intranets. We consider the classification problem on a corpus that has been processed primarily for the purpose of searching, and thus our access to documents is solely through the inverted index of a large scale search engine. Our main goal is to build the "best" short query that characterizes a document class using operators normally available within large engines. We show that surprisingly good classification accuracy can be achieved on average over multiple classes by queries with as few as 10 terms. Moreover, we show that optimizing the efficiency of query execution by careful selection of these terms can further reduce the query costs. More precisely, we show that on our set-up the best 10 terms query canachieve 90% of the accuracy of the best SVM classifier (14000 terms), and if we are willing to tolerate a reduction to 86% of the best SVM, we can build a 10 terms query that can be executed more than twice as fast as the best 10 terms query.
Pruning strategies for mixed-mode querying
Authors: Vo Ngoc Anh, Alistair Moffat
Venue: CIKM
Year: 2006

Web information retrieval systems face a range of unique challenges, not the least of which is the sheer scale of the data that must be handled. Also specific to web retrieval is that queries may be a mix of Boolean and ranked features, and documents may have static score components that must also be factored into the ranking process. In this paper we consider a range of query semantics used in web retrieval systems, and show that impact-sorted indexes provide support for dynamic pruning mechanisms and in doing so allow fast document-at-a-time resolution of typical mixed-mode queries, even on relatively large volumes of data. Our techniques also extend to more complex query semantics, including the use of phrase, proximity, and structural constraints.
3DString: a feature string kernel for 3D object classification on voxelized data
Authors: Johannes Aßfalg, Karsten M. Borgwardt, Hans-Peter Kriegel
Venue: CIKM
Year: 2006

Classification of 3D objects remains an important task in many areas of data management such as engineering, medicine or biology. As a common preprocessing step in current approaches to classification of voxelized 3D objects, voxel representations are transformed into a feature vector description.In this article, we introduce an approach of transforming 3D objects into feature strings which represent the distribution of voxels over the voxel grid. Attractively, this feature string extraction can be performed in linear runtime with respect to the number of voxels. We define a similarity measure on these feature strings that counts common k-mers in two input strings, which is referred to as the spectrum kernel in the field of kernel methods. We prove that on our feature strings, this similarity measure can be computed in time linear to the number of different characters in these strings. This linear runtime behavior makes our kernel attractive even for large datasets that occur in many application domains. Furthermore, we explain that our similarity measure induces a metric which allows to combine it with an M-tree for handling of large volumes of data. Classification experiments on two published benchmark datasets show that our novel approach is competitive with the best state-of-the-art methods for 3D object classification.
IR principles for content-based indexing and retrieval of functional brain images
Authors: Bing Bai, Paul B. Kantor, Nicu D. Cornea, Deborah Silver
Venue: CIKM
Year: 2006

In this paper, we explore the concept of a "library of brain images", which implies not only a repository of brain images, but also efficient search and retrieval mechanisms that are based on models derived from IR practice. As a preliminary study, we have worked with a collection of functional MRI brain images assembled in the study of several distinct cognitive tasks. We adapt several classical IR methods (inverted indexing, TFIDF and Latent Semantic Indexing(LSI)) to content-based brain image retrieval. Our results show that efficient and accurate retrieval of brain images is possible, and that representations motivated by the IR perspective are somewhat more effective than are methods based on retaining the full image information.
A data stream language and system designed for power and extensibility
Authors: Yijian Bai, Hetal Thakkar, Haixun Wang, Chang Luo, Carlo Zaniolo
Venue: CIKM
Year: 2006

By providing an integrated and optimized support for user-defined aggregates (UDAs), data stream management systems (DSMS) can achieve superior power and generality while preserving compatibility with current SQL standards. This is demonstrated by the Stream Mill system that, through is Expressive Stream Language (ESL), efficiently supports a wide range of applications - including very advanced ones such as data stream mining, streaming XML processing, time-series queries, and RFID event processing. ESL supports physical and logical windows (with optional slides and tumbles) on both built-in aggregates and UDAs, using a simple framework that applies uniformly to both aggregate functions written in an external procedural languages and those natively written in ESL. The constructs introduced in ESL extend the power and generality of DSMS, and are conducive to UDA-specific optimization and efficient execution as demonstrated by several experiments.
Secure search in enterprise webs: tradeoffs in efficient implementation for document level security
Authors: Peter Bailey, David Hawking, Brett Matson
Venue: CIKM
Year: 2006

Document level security (DLS) -- enforcing permissions prevailing at the time of search -- is specified as a mandatory requirement in many enterprise search applications. Unfortunately, depending upon implementation details and values of key parameters, DLS may come at a high price in increased query processing time, leading to an unacceptably slow search experience. In this paper we present a model and a method for carrying out secure search in the presence of DLS within enterprise webs. We report on two alternative commercial DLS search implementations. Using a 10,000 document experimental DLS environment, we graph the dependence of query processing time on result set size and visibility density for different classes of user. Scaled up to collections of tens of thousands of documents, our results suggest that query times will be unacceptable if exact counts of matching documents are required and also for users who can view only a small proportion of documents. We show that the time to conduct access checks is dramatically increased if requests must be sent off-server, even on a local network, and discuss methods for reducing the cost of security checks. We conclude that enterprises can effectively reduce DLS overheads by organizing documents in such a way that most access checking can be at collection rather than document level, by forgoing accurate match counts, by using caching, batching or hierarchical methods to cut costs of DLS checking and, if applicable, by using a single portal both to access and search documents.
Automatically constructing collections of online database directories
Authors: Luciano Barbosa, Juliana Freire
Venue: CIKM
Year: 2006

Due the the explosion in the number of online databases, there has been increased interest in leveraging the highquality information present in these databases [6, 1, 8]. However, finding the right databases can be very challenging. For example, if a biologist needs to locate databases related to molecular biology and searches on Google for the keywords “molecular biology database” over 27 million documents are returned. Among these, she will find pages that contain databases, but the results also include a very large number of pages from journals, scientific articles, etc. Recognizing the need for better mechanisms to locate online databases, people have started to create online database collections such as the Molecular Biology Database Collection [4], which lists databases of value to biologists. This collection, however, has been manually created and is manually maintained by the National Library of Medicine. Since it is estimated that there are over 20 million online databases [6], manual approaches to this problem are not practical. Besides, since new databases are constantly being added, the coverage of a manually maintained collection can be greatly compromised. In this paper, we describe a new approach to the problem of automatically locating and organizing online databases that belong to a given domain. There are a number of issues that make this problem particularly challenging. Since online databases are sparsely distributed on the Web, an efficient strategy is needed to locate the forms that serve as entry points to these databases. In addition, online databases do not publish their schemas and their contents are often hard to retrieve. Thus, a scalable solution must determine the relevance of a form to a given database domain by examining just the information available in (and around) the form. As shown in Figure 1, our framework for constructing topic-specific online database collections consists of two key
SaLSa: computing the skyline without scanning the whole sky
Authors: Ilaria Bartolini, Paolo Ciaccia, Marco Patella
Venue: CIKM
Year: 2006

Skyline queries compute the set of Pareto-optimal tuples in a relation, ie those tuples that are not dominated by any other tuple in the same relation. Although several algorithms have been proposed for efficiently evaluating skyline queries, they either require to extend the relational server with specialized access methods (which is not always feasible) or have to perform the dominance tests on all the tuples in order to determine the result. In this paper we introduce SaLSa (Sort and Limit Skyline algorithm), which exploits the sorting machinery of a relational engine to order tuples so that only a subset of them needs to be examined for computing the skyline result. This makes SaLSa particularly attractive when skyline queries are executed on top of systems that do not understand skyline semantics or when the skyline logic runs on clients with limited power and/or bandwidth.
Capturing community search expertise for personalized web search using snippet-indexes
Authors: Oisín Boydell, Barry Smyth
Venue: CIKM
Year: 2006

We describe and evaluate an approach to capturing and re-using search expertise within a community of like minded searchers, such as the employees of a company or organisation. Within knowledge based industries, search expertise - the ability to quickly and accurately locate information according to a specific information need - is an important corporate asset and in our approach we attempt to capture this knowledge by mining the title and snippet texts of results that have been selected by community members in response to their queries. Our assumption is that the snippet text of a result must play a role in helping users to judge the initial relevance of that result and that the snippet terms of selected results must contain especially informative terms about the goals and preferences of the searchers. In other words, results are selected because the user recognises certain combinations of terms in their snippets which are related to their information needs. Our approach seeks to build a community-based snippet index that reflects the evolving interests of a group of searchers. This index is then used to re-rank the results returned by some underlying search engine by boosting the ranking of key results that have been frequently selected for similar queries by community members in the past.
Constructing better document and query models with markov chains
Authors: Guihong Cao, Jian-Yun Nie, Jing Bai
Venue: CIKM
Year: 2006

Document and query expansions have been used separately in previous studies to enhance the representation of documents and queries. In this paper, we propose a general method that integrates both of them. Expansion is carried out using multi-stage Markov chains. Our experiments show that this method significantly outperforms the existing approaches.
Ranking web objects from multiple communities
Authors: Le Chen, Lei Zhang, Feng Jing, Kefeng Deng, Wei-Ying Ma
Venue: CIKM
Year: 2006

Vertical search is a promising direction as it leverages domain-specific knowledge and can provide more precise information for users. In this paper, we study the Web object-ranking problem, one of the key issues in building a vertical search engine. More specifically, we focus on this problem in cases when objects lack relationships between different Web communities, and take high-quality photo search as the test bed for this investigation. We proposed two score fusion methods that can automatically integrate as many Web communities (Web forums) with rating information as possible. The proposed fusion methods leverage the hidden links discovered by a duplicate photo detection algorithm, and aims at minimizing score differences of duplicate photos in different forums. Both intermediate results and user studies show the proposed fusion methods are practical and efficient solutions to Web object ranking in cases we have described. Though the experiments were conducted on high-quality photo ranking, the proposed algorithms are also applicable to other ranking problems, such as movie ranking and music ranking.
Efficient join processing over uncertain data
Authors: Reynold Cheng, Sarvjeet Singh, Sunil Prabhakar, Rahul Shah, Jeffrey Scott Vitter, Yuni Xia
Venue: CIKM
Year: 2006

In many applications data values are inherently uncertain. This includes moving-objects, sensors and biological databases. There has been recent interest in the development of database management systems that can handle uncertain data. Some proposals for such systems include attribute values that are uncertain. In particular, an attribute value can be modeled as a range of possible values, associated with a probability density function. Previous efforts for this type of data have only addressed simple queries such as range and nearest-neighbor queries. Queries that join multiple relations have not been addressed in earlier work despite the significance of joins in databases. In this paper we address join queries over uncertain data. We propose a semantics for the join operation, define probabilistic operators over uncertain data, and propose join algorithms that provide efficient execution of probabilistic joins. The paper focuses on an important class of joins termed probabilistic threshold joins that avoid some of the semantic complexities of dealing with uncertain data. For this class of joins we develop three sets of optimization techniques: item-level, page-level, and index-level pruning. These techniques facilitate pruning with little space and time overhead, and are easily adapted to most join algorithms. We verify the performance of these techniques experimentally.
Query taxonomy generation for web search
Authors: Pu-Jen Cheng, Ching-Hsiang Tsai, Chen-Ming Hung, Lee-Feng Chien
Venue: CIKM
Year: 2006

We propose an approach that organizes the search-result clusters into a hierarchical structure, called a query taxonomy, from the user's perspective. The proposed approach is based on an unsupervised classification method, which uses the dynamic Web as the training corpus. With query taxonomy, users can browse relevant Web documents more conveniently and comprehensibly. Our experimental results verify the feasibility and the effectiveness of the proposed approach to query taxonomy generation in Web search.
Summarizing local context to personalize global web search
Authors: Paul-Alexandru Chirita, Claudiu S. Firan, Wolfgang Nejdl
Venue: CIKM
Year: 2006

The PC Desktop is a very rich repository of personal information, efficiently capturing user's interests. In this paper we propose a new approach towards an automatic personalization of web search in which the user specific information is extracted from such local desktops, thus allowing for an increased quality of user profiling, while sharing less private information with the search engine. More specifically, we investigate the opportunities to select personalized query expansion terms for web search using three different desktop oriented approaches: summarizing the entire desktop data, summarizing only the desktop documents relevant to each user query, and applying natural language processing techniques to extract dispersive lexical compounds from relevant desktop resources. Our experiments with the Google API showed at least the latter two techniques to produce a very strong improvement over current web search.
Query optimization using restructured views
Authors: Rada Chirkova, Fereidoon Sadri
Venue: CIKM
Year: 2006

We study optimization of relational queries using materialized views, where views may be regular or restructured. In a restructured view, some data from the base table(s) are represented as metadata - that is, schema information, such as table and attribute names - or vice versa.Using restructured views in query optimization opens up a new spectrum of views that were not previously available, and can result in significant additional savings in query-evaluation costs. These savings can be obtained due to a significantly larger set of views to choose from, and may involve reduced table sizes, elimination of self-joins, clustering produced by restructuring, and horizontal partitioning.In this paper we propose a general query-optimization framework that treats regular and restructured views in a uniform manner and is applicable to SQL select-project-join queries and views with or without aggregation. Within the framework we provide (1) algorithms to determine when a view (regular or restructured) is usable in answering a query, and (2) algorithms to rewrite a query using usable views.Semantic information, such as knowledge of the key of a view, can be used to further optimize a rewritten query. Within our general query-optimization framework, we develop techniques for determining the key of a (regular or restructured) view, and show how this information can be used to further optimize a rewritten query. It is straightforward to integrate all our algorithms and techniques into standard query-optimization algorithms.
Search result summarization and disambiguation via contextual dimensions
Authors: Krishna Prasad Chitrapura, Sachindra Joshi, Raghu Krishnapuram
Venue: CIKM
Year: 2006

Topic hierarchies are a popular method of summarizing the results obtained in response to a query in various search applications. However, topic hierarchies are rigid when they are pre-defined and somewhat unintuitive when they are dynamically generated by statistical techniques. In this paper, we propose an alternative approach to query disambiguation and result summarization by placing the results in set of contextual dimensions which can be viewed as facets. For the generic search scenario, we illustrate our approach by using three types of contextual dimensions, namely, concepts, features, and specializations. We use NLP techniques and a data mining algorithm to select distinct contexts.
On subspace clustering with density consciousness
Authors: Yi-Hong Chu, Jen-Wei Huang, Kun-Ta Chuang, Ming-Syan Chen
Venue: CIKM
Year: 2006

In this paper, a problem, called "the density divergence problem" is explored. This problem is related to the phenomenon that the densities of the clusters vary in different subspace cardinalities. We take the densities into consideration in subspace clustering and explore an algorithm to adaptively determine different density thresholds to discover clusters in different subspace cardinalities.
Validating associations in biological databases
Authors: Francisco M. Couto, Mário J. Silva, Pedro Coutinho
Venue: CIKM
Year: 2006

Erroneous data can often be found in databases, and detecting it is normally a non-trivial task. For example, To cope with the large amount of biological sequences being produced, a significant number of genes and proteins have been annotated by automated tools. A protein annotation is an association between a protein and a term describing its role. These tools have produced a significant number of misannotations that are now present in biological databases. This paper proposes a new method for automatically scoring associations by comparing them to preexisting curated associations. An association is a pair that links two entities. The score can be used to filter incorrect or uncommon associations.We evaluated the method using the automated protein annotations submitted to BioCreAtIvE, an international evaluation of state-of-the-art text-mining systems in Biology. The method scored each of these annotations and those scored below a certain threshold were discarded. The results have shown a small trade-off in recall for a large improvement in precision. For example, we were able to discard 44.6%, 66.8% and 81% of the misannotations, maintaining 96.9%, 84.2%, and 47.8% of the correct annotations, respectively. Moreover, we were able to outperform each individual submission to BioCreAtIvE by proper adjustment of the threshold.
Query-specific clustering of search results based on document-context similarity scores
Authors: Edward K. F. Dang, Robert W. P. Luk, Dik Lun Lee, Kei Shiu Ho, Stephen Chi-fai Chan
Venue: CIKM
Year: 2006

This paper presents a pilot study of query-specific clustering that uses our novel document-context based similarity scores as compared with document similarity scores. Clustering is applied to the top 1000 retrieved documents for a given query. Clustering effectiveness is evaluated based on the MK1 score for TREC-2, TREC-6 and TREC-7 test collections. Encouraging results were obtained whereby document-context clustering produces better MK1 scores than document clustering with a 95% confidence level if precision and recall are equally important.