OpenRaiser/Intern-Atlas huggingface dataset:
Optimal proactive caching in peer-to-peer network: analysis and application
Authors: Weixiong Rao, Lei Chen, Ada Wai-Chee Fu, Yingyi Bu
Venue: CIKM
Year: 2007

As a promising new technology with the unique properties like high efficiency, scalability and fault tolerance, Peer-to-Peer (P2P) technology is used as the underlying network to build new Internet-scale applications. However, one of the well known issues in such an application (for example WWW) is that the distribution of data popularities is heavily tailed with a Zipf-like distribution. With consideration of the skewed popularity we adopt a proactive caching approach to handle the challenge, and focus on two key problems: where (i.e. the placement strategy: where to place the replicas) and how (i.e. the degree problem: how many replicas are assigned to one specific content)? For the where problem, we propose a novel approach which can be generally applied to structured P2P networks. Next, we solve two optimization objectives related to the how problem: MAX_PERF and MIN_COST. Our solution is called <B>PoPCache</B>, and we discover two interesting properties: (1) the number of replicas assigned to each content is proportional to its popularity; (2) the derived optimal solutions are related to the entropy of popularity. To our knowledge, none of the previous works has mentioned such results. Finally, we apply the results of PoPCache to propose a P2P base web caching, called as Web-PoPCache. By means of web cache trace driven simulation, our extensive evaluation results demonstrate the advantages of PoPCache and Web-PoPCache.
Management of data with uncertainties
Authors: Christopher Ré, Dan Suciu
Venue: CIKM
Year: 2007

Since their invention in the early 70s, relational databases have been deterministic. They were designed to support applications s.a. accounting, inventory, customer care, and manufacturing, and these applications require a precise semantics. Thus, database systems are deterministic. A row is either in the database or is not; a tuple is either in the query answer or is not. The foundations of query processing and the tools that exists today for managing data rely fundamentally on the assumption that the data is deterministic. Increasingly, today we need to manage data that is uncertain. The uncertainty can be in the data itself, in the schema, in the mapping between different data instances, or in the user query. We find increasingly large amounts of uncertain data in a variety of domains: in data integration, in scientific data, in information extracted automatically from text, in data from the physical world. Large enterprises today can sometimes afford to cope with the uncertainty in their data by completely removing it, by using some expensive data cleaning or ETL tools. But increasingly today organizations or users need to cope directly with uncertain data, either because cleaning it is prohibitively expensive (e.g. in scientific data integration or in integration of Web data), or because it is even impossible to clean (e.g. sensor data or RFID data). It becomes clear that we need
Semantic verification in an online fact seeking environment
Authors: Dmitri Roussinov, Ozgur Turetken
Venue: CIKM
Year: 2007

Many artificial intelligence tasks, such as automated question answering, reasoning or heterogeneous database integration, involve verification of a semantic category (e.g. "coffee" is a drink, "red" is a color, while "steak" is not a drink and "big" is not a color). We present a novel algorithm to automatically validate a semantic category. Contrary to the methods suggested earlier, our approach does not rely on any manually codified knowledge but instead capitalizes on the diversity of topics and word usage on the World Wide Web. We have tested our approach within our online fact-seeking (question answering) environment. When tested on the TREC questions that expect the answer to belong to a specific semantic category, our approach has improved the accuracy by up to 14% depending on the model and metrics used.
Webview selection from user access patterns
Authors: Samia Saidi, Yahya Slimani, Khedija Arour
Venue: CIKM
Year: 2007

The number of Web Usage Mining (WUM) applications is growing continuously, especially due to the business interest in e-commerce Web sites and the related Web-marketing applications.The application of WUM results goes beyond the subject of our thesis since one important part of our thesis deals with the problem of selection of WebViews using technicsof WUM. View materialization is an important issue ifwe want to improve the efficiency of many applications likeOLAP, Database and Web applications. In this proposal wesuggest a novel approach for selecting webviews to be materialized in order to optimize the response time of web queries since satisfying the needs of users is vital for Web sites. The selection of Webviews to be materialized was mainly based on the estimation of metrics requiring hard collects of multiple statistics [10] that's why, we believe on a solution based on mining an interesting set of webviews to be materialized from realistic data: Web log files. Thus, Web log files will be parsed, analyzed and treated to give a set of webviews, based on frequent closed itemsets.
"More like these": growing entity classes from seeds
Authors: Luís Sarmento, Valentin Jijkoun, Maarten de Rijke, Eugénio C. Oliveira
Venue: CIKM
Year: 2007

We present a corpus-based approach to the class expansion task. For a given set of seed entities we use co-occurrence statistics taken from a text collection to define a membership function that is used to rank candidate entities for inclusion in the set. We describe an evaluation framework that uses data from Wikipedia. The performance of our class extension method improves as the size of the text collection increases.
Mining semantic distance between corpus terms
Authors: Ahmad El Sayed, Hakim Hacid, Djamel A. Zighed
Venue: CIKM
Year: 2007

In this paper, we face two problems in classical semantic similarity measures. Firstly, the context-dependency problem in knowledge-base measures since no one takes into account the context of the target domain. That is, a multisource context-dependent approach is presented. Secondly, the coverage problem with these measures since similarities can only be calculated between concepts included in a taxonomy. Moreover, "pure" corpus-based measures are still way from achieving performance reached by knowledge based measures. We present a more complex corpus-based approach using a taxonomy and data mining techniques in order to compute semantic distances between terms uncovered by the taxonomy. Experiments made show clearly the effectiveness of both proposed approaches.
Managing highly correlated semi-structured data: architectural aspects of a digital archive
Authors: Alf-Christian Schering, Holger Meyer, Andreas Heuer
Venue: CIKM
Year: 2007

XML techniques are well suited to describe, manage, store, and exchange hierarchical, semi-structured data. Information represented beyond hierarchical structures can still be described and exchanged in XML format employing additional concepts such as ID/IDREF or XLink. However, retrieval, manipulation, and storage mechanisms are far away from being the ideal solution for such data. Query languages do not perform efficiently in these cases. Especially in scenarios, such as the Digital Wossidlo Archive (WossiDiA), a project dealing with a huge number of arbitrarily correlated data units, XML query evaluation and retrieval techniques face problems, such as intricate querying and bad efficiency. At this point a solution to manage these data efficiently needs to be devised. This paper introduces a first approach which attempts to find such a solution for the WossiDiA information system.
Reasoning about vague topological information
Authors: Steven Schockaert, Martine De Cock
Venue: CIKM
Year: 2007

Topological information plays a fundamental role in the human perception of spatial configurations and is thereby one of the most prominent geographical features in natural language. As vagueness abounds in geography, flexible formalisms with the ability to capture vague topological information are often needed in practice. While such formalisms have already been introduced by various authors, complete reasoning procedures are usually not discussed. In this paper, we show how many interesting reasoning tasks, such as consistency checking and entailment checking, can be supported in a generalization of the well-known RCC-8 calculus. In particular, we present decision procedures based on linear programming, solving all reasoning tasks of interest. We furthermore show how deciding the consistency of vague topological information can be reduced to the consistency problem of the original RCC-8.
An on-line interactive method for finding association rules data streams
Authors: Se Jung Shin, Won Suk Lee
Venue: CIKM
Year: 2007

In order to trace the changes of association rules over an online data stream efficiently, this paper proposes two different methods of generating all association rules directly over the changing set of currently frequent itemsets. While all of the currently frequent itemsets are monitored by the estDec method, all the association rules of every frequent itemset in the prefix tree of the estDec method are generated. For this purpose, a traversal stack is introduced to efficiently enumerate all association rules. These online methods can avoid the drawbacks of the conventional two-step approach. In an on-line environment, a user may be interested in finding those association rules whose antecedents or consequents are fixed to be a specific itemset. Since generating all the association rules may take too long to produce them timely, two additional methods, namely Assoc-X and Assoc-Y, are introduced. Finally, the proposed methods are compared by a series of experiments to identify their various characteristics.
Formalizing ontology reconciliation techniques as a basis for meaningful mediation in service-related tasks
Authors: Patrício de Alencar Silva, Cláudia M. F. A. Ribeiro, Ulrich Schiel
Venue: CIKM
Year: 2007

With the advent of Semantic Web, the fast dissemination of ontologies to represent and share information causes a deep impact on knowledge retrieval, as a whole. In this context, the use of different ontologies to express meaning on the same application domain leads to a kind of "Tower of Babel Effect" on the Web, bringing new problems to the communication among different applications. This problem still remains in service-oriented architectures, considering that a same service can be described by the use of different ontologies and standards. Therefore, the urge of an ontology reconciliation approach arises in order to enable communication despite the differences. This paper focuses on providing a formal description of ontology reconciliation techniques, such as merging, alignment and integration, to provide better understanding of how these techniques can be used on the scope of Semantic Web Services Architecture.
Probabilistic correlation-based similarity measure of unstructured records
Authors: Shaoxu Song, Lei Chen
Venue: CIKM
Year: 2007

Computing the similarity between unstructured records is a fundamental function in multiple applications. Approximate string matching and full text retrieval techniques do not show the best performance when applied directly, since the information are limited in unstructured records of short record length. In this paper, we propose a novel probabilistic correlation-based similarity measure. Rather than simply conducting the exact matching tokens of two records, our similarity evaluation enriches the information of records by considering the correlations of tokens. We define the probabilistic correlation between tokens as the probability that these tokens appear in the same records. Then we compute the weight of tokens and discover the correlations of records based on the probabilistic correlations of tokens. Finally, we present extensive experimental results to demonstrate the effectiveness of our approach.
Ranking with semi-supervised distance metric learning and its application to housing potential estimation
Authors: Yangqiu Song, Bin Zhang, Wen Jun Yin, Changshui Zhang, Jin Dong
Venue: CIKM
Year: 2007

This paper proposes a semi-supervised distance metric learning algorithm for the ranking problem. Instead of giving the computer what are the important factors that affect the final rank value, we only give several most certainly ranked points which implicitly contain the knowledge of the ranking factors. Then the computer can automatically use the most certain points and plenty of unlabeded data to learn an informative metric for ranking. This metric not only can help to regress an order in the observed data, but also can be used to retrieve the data by querying new test points. Moreover, the lower-rank distance metric can be used to visualize high-dimensional data. We also present an application to the housing potential estimation problem. It is shown that the algorithm is efficient to help consultants to refine their consulting work.
Evaluation of partial path queries on xml data
Authors: Stefanos Souldatos, Xiaoying Wu, Dimitri Theodoratos, Theodore Dalamagas, Timos K. Sellis
Venue: CIKM
Year: 2007

XML query languages typically allow the specification of structural patterns of elements. Finding the occurrences of such patterns in an XML tree is the key operation in XML query processing. Many algorithms have been presented for this operation. These algorithms focus mainly on the evaluation of path-pattern or tree-pattern queries. In this paper, we define a partial path-pattern query language, and we address the problem of its efficient evaluation on XML data.
SLOQUE: slot-based query expansion for complex questions
Authors: Maggy Anastasia Suryanto, Ee-Peng Lim, Aixin Sun, Roger H. L. Chiang
Venue: CIKM
Year: 2007

Searching answers to complex questions is a challenging IR task. In this paper, we examine the use of query templates with semantic slots to formulate slot-based queries. These queries have query terms assigned to entity and relationship slots. We develop several query expansion methods for slot-based queries so as to improve their retrieval effectiveness on a document collection. Each method consists of a combination of term scoring scheme, term scoring formula, and term assignment scheme. Our preliminary experiments evaluate these different slot-based query expansion methods on a collection of news documents,and conclude that:(1) slot-based queries yield better retrieval accuracy compared to keyword-based queries in the complex question problems; and (2)directly applying traditional query expansion on the query terms of each slot does not always work well.
Designing clustering-based web crawling policies for search engine crawlers
Authors: Qingzhao Tan, Prasenjit Mitra, C. Lee Giles
Venue: CIKM
Year: 2007

The World Wide Web is growing and changing at an astonishing rate. Web information systems such as search engines have to keep up with the growth and change of the Web. Due to resource constraints, search engines usually have difficulties keeping the local database completely synchronized with the Web. In this paper, we study how tomake good use of the limited system resource and detect as many changes as possible. Towards this goal, a crawler for the Web search engine should be able to predict the change behavior of the webpages. We propose applying clustering-based sampling approach. Specifically, we first group all the local webpages into different clusters such that each cluster contains webpages with similar change pattern. We then sample webpages from each cluster to estimate the change frequency of all the webpages in that cluster. Finally, we let the crawler re-visit the cluster containing webpages with higher change frequency with a higher probability. To evaluate the performance of an incremental crawler for a Web search engine, we measure both the freshness and the quality of the query results provided by the search engine. We run extensive experiments on a real Web data set of about 300,000 distinct URLs distributed among 210 websites. The results demonstrate that our clustering algorithm effectively clusters the pages with similar change patterns, and our solution significantly outperforms the existing methods in that it can detect more changed webpages and improve the quality of the user experience for those who query the search engine.
Sigma encoded inverted files
Authors: Andrew Trotman, Vikram Subramanya
Venue: CIKM
Year: 2007

Compression of term frequency lists and very long document-id lists within an inverted file search engine are examined. Several compression schemes are compared including Elias γ and δ codes, Golomb Encoding, Variable Byte Encoding, and a class of word-based encoding schemes including Simple-9, Relative-10 and Carryover-12. It is shown that these compression methods are not well suited to compressing these kinds of lists of numbers. Of those tested, Carryover-12 is preferred because it is both effective at compression and fast at decompression.
Dynamic index pruning for effective caching
Authors: Yohannes Tsegay, Andrew Turpin, Justin Zobel
Venue: CIKM
Year: 2007

RAM and dynamic pruning schemes to reduce query evaluation times. While only a small portion of lists are processed with dynamic pruning, current systems still store the entire inverted list in cache. In this paper we investigate caching only the pieces of the inverted lists that are actually used to answer a query during dynamic pruning. We examine an LRU cache model, and two recently proposed models. We also introduce a new dynamic pruning scheme for impact-ordered inverted lists.
Efficient search ranking in social networks
Authors: Monique V. Vieira, Bruno M. Fonseca, Rodrigo Damazio, Paulo Braz Golgher, Davi de Castro Reis, Berthier A. Ribeiro-Neto
Venue: CIKM
Year: 2007

In social networks such as Orkut, www.orkut.com, a large portion of the user queries refer to names of other people. Indeed, more than 50% of the queries in Orkut are about names of other users, with an average of 1.8 terms per query. Further, the users usually search for people with whom they maintain relationships in the network. These relationships can be modelled as edges in a friendship graph, a graph in which the nodes represent the users. In this context, search ranking can be modelled as a function that depends on the distances among users in the graph, more specifically, of shortest paths in the friendship graph. However, application of this idea to ranking is not straightforward because the large size of modern social networks (dozens of millions of users) prevents efficient computation of shortest paths at query time. We overcome this by designing a ranking formula that strikes a balance between producing good results and reducing query processing time. Using data from the Orkut social network, which includes over 40 million users, we show that our ranking, augmented by this new signal, produces high quality results, while maintaining query processing time small.
Towards a SOA infrastructure for statistically analysing public health data
Authors: Pierpaolo Vittorini, Stefano Necozione, Ferdinando di Orio
Venue: CIKM
Year: 2007

To respond to the need for interoperable information systems in public health, several proposals based on XML-related technologies are currently available. For instance, the CDA [8] is an architecture developed by the HL7 organization for representing and managing clinical documents, while the PHIN [12] is a CDC infrastructure whose aim is to automatically exchange XML data between public health partners through ebXML compliant SOAP web services [16, 11].
Temporal constraints for rule-based event processing
Authors: Karen Walzer, Alexander Schill, Alexander Löser
Venue: CIKM
Year: 2007

Complex event processing (CEP) is an important technology for event-driven systems with a broad application space ranging from supply chain management for RFID, systems monitoring, and stock market analysis to news services. The purpose of CEP is the identification of patterns of events with logical, temporal or causal relationships out of single occurring events.
Translating topics to words for image annotation
Authors: Yong Wang, Shaogang Gong
Venue: CIKM
Year: 2007

One of the classic techniques for image annotation is the language translation model. It views an image as a document, i.e., a set of visual words which are obtained by vector quatitizing the image regions generated by unsupervised image segmentation. Annotating images are achieved by translating visual words to textual words, just like translating a document in English to a document in French. In this paper, we also view an image as a document, but we view the annotation processes as two consecutive processes, i.e., document summarization and translation. In the document summarization process, an image document is firstly summarized into its own visual language, which we called visual topics. The translation process translates these visual topics to textual words. Compared to the original translation model, our visual topics learned by the probabilistic latent semantic analysis (PLSA) approach provide an intermediate abstract level of visual description. We show improved annotation performance on the Corel image dataset.
Learning query-biased web page summarization
Authors: Changhu Wang, Feng Jing, Lei Zhang, Hong-Jiang Zhang
Venue: CIKM
Year: 2007

Query-biased Web page summarization is the summarization of a Web page reflecting the relevance of it to a specific query. It plays an important role in search results representation of Web search engines. In this paper, we propose a learning-based query-biased Web page summarization method. The summarization problem is solved within the typical sentence selection framework. Different from existing Web page summarization methods that use page content or link context alone, both of them are considered as the sources of sentences in this work. Most of existing learning-based summarization methods treat summarization as a sentence classification problem and train a classifier to discriminate between extracted sentences and non-extracted sentences of all training documents. The basic assumption of these methods is that sentences from different documents are comparable with respect to the class information. In contrast to the classification scheme, a ranking scheme is introduced to rank extracted sentences higher than non-extracted sentences of each training document. The underlying assumption that sentences within a document are comparable is weaker and more reasonable than the assumption of classification-based scheme. Extensive results using intrinsic evaluation metrics gauge many aspects of the proposed method.
Reconstructing ddc for interactive classification
Authors: Jun Wang, Meng Chen Lee
Venue: CIKM
Year: 2007

The automated text categorization (TC) has made prominent progress in recent years. However, seldom work is done on automatic classification with library classification systems, the largest and most sophisticated classification systems people ever built, such as the Dewey Decimal classification (DDC). The library classification is a very laborious and time-consuming job that requires qualification and good training.