OpenRaiser/Intern-Atlas huggingface dataset:
Valid scope computation for location-dependent spatial query in mobile broadcast environments
Authors: Ken C. K. Lee, Josh Schiffman, Baihua Zheng, Wang-Chien Lee
Venue: CIKM
Year: 2008

Wireless data broadcast is an efficient and scalable means to provide information access for a large population of clients in mobile environments. With Location-Based Services (LBSs) deployed upon a broadcast channel, mobile clients can collect data from the channel to answer their location-dependent spatial queries (LDSQs). Since the results of LDSQs would become invalid when mobile client moves to new locations, the knowledge of valid scopes for LDSQ results is necessary to assist clients to determine if their previous LDSQ results can be reused after they moved. This effectively improves query response time and client energy consumption. In this paper, we devise efficient algorithms to determine valid scopes for various LDSQs including range, window and nearest neighbor queries along with LDSQ processing over a broadcast channel. We conduct an extensive set of experiments to evaluate the performance of our proposed algorithms. While the proposed valid scope algorithm incurs only little extra processing overhead, unnecessary LDSQ reevaluation is significantly eliminated, thus providing faster query response and saving client energy.
Tag-geotag correlation in social networks
Authors: Sang Su Lee, Dongwoo Won, Dennis McLeod
Venue: CIKM
Year: 2008

This paper presents an analysis of the correlation of annotated information unit (textual) tags and geographical identification metadata geotags. Despite the increased usage of geotagging in collaborative tagging systems, most current research focuses on textual tagging alone in solving the tag search problem. This may result in difficulties to search for precise and relevant information within the given tag space. For example, inconsistencies like polysemy, synonyms, and word inflections with plural forms complicate the tag search problem. Therefore, more work needs to be done to include geotag information with existing tagging information for analysis. In this paper, to make geotagging possible to be used in analysis with tagging, we prove that there is a strong correlation between tagging and geotagging information. Our approach uses tag similarity and geographical distribution similarity to determine inter-relationships among tags and geotags. From our initial experiments, we show that the power law is established between tag similarity and geographical distribution similarity: this means that tag similarity and geographical distribution similarity has a strong correlation and the correlation can be used to find more relevant tags in the tag space. The power law confirms that there is an increased relationship between tagging and geotagging and the increased relationship is scalable in size of tags and geotags. Also, using both geotagging and tagging information instead of only tagging, we show that the uncertainty between derived and actual similarities among tags is reduced.
Scalable community discovery on textual data with relations
Authors: Huajing Li, Zaiqing Nie, Wang-Chien Lee, C. Lee Giles, Ji-Rong Wen
Venue: CIKM
Year: 2008

Every piece of textual data is generated as a method to convey its authors' opinion regarding specific topics. Authors deliberately organize their writings and create links, i.e., references, acknowledgments, for better expression. Thereafter, it is of interest to study texts as well as their relations to understand the underlying topics and communities. Although many efforts exist in the literature in data clustering and topic mining, they are not applicable to community discovery on large document corpus for several reasons. First, few of them consider both textual attributes as well as relations. Second, scalability remains a significant issue for large-scale datasets. Additionally, most algorithms rely on a set of initial parameters that are hard to be captured and tuned. Motivated by the aforementioned observations, a hierarchical community model is proposed in the paper which distinguishes community cores from affiliated members. We present our efforts to develop a scalable community discovery solution for large-scale document corpus. Our proposal tries to quickly identify potential cores as seeds of communities through relation analysis. To eliminate the influence of initial parameters, an innovative attribute-based core merge process is introduced so that the algorithm promises to return consistent communities regardless initial parameters. Experimental results suggest that the proposed method has high scalability to corpus size and feature dimensionality, with more than 15 topical precision improvement compared with popular clustering techniques.
Effective pattern taxonomy mining in text documents
Authors: Yuefeng Li, Sheng-Tang Wu, Xiaohui Tao
Venue: CIKM
Year: 2008

Many data mining techniques have been proposed for mining useful patterns in databases. However, how to effectively utilize discovered patterns is still an open research issue, especially in the domain of text mining. Most existing methods adopt term-based approaches. However, they all suffer from the problems of polysemy and synonymy. This paper presents an innovative technique, pattern taxonomy mining, to improve the effectiveness of using discovered patterns for finding useful information. Substantial experiments on RCV1 demonstrate that the proposed solution achieves encouraging performance.
A two-stage text mining model for information filtering
Authors: Yuefeng Li, Xujuan Zhou, Peter Bruza, Yue Xu, Raymond Y. K. Lau
Venue: CIKM
Year: 2008

Mismatch and overload are the two fundamental issues regarding the effectiveness of information filtering. Both term-based and pattern (phrase) based approaches have been employed to address these issues. However, they all suffer from some limitations with regard to effectiveness. This paper proposes a novel solution that includes two stages: an initial topic filtering stage followed by a stage involving pattern taxonomy mining. The objective of the first stage is to address mismatch by quickly filtering out probable irrelevant documents. The threshold used in the first stage is motivated theoretically. The objective of the second stage is to address overload by apply pattern mining techniques to rationalize the data relevance of the reduced document set after the first stage. Substantial experiments on RCV1 show that the proposed solution achieves encouraging performance.
Energy-efficient skyline query processing and maintenance in sensor networks
Authors: Weifa Liang, Baichen Chen, Jeffrey Xu Yu
Venue: CIKM
Year: 2008

The skyline query, as an important operator in databases for multi-preference analysis and decision making, has received much attention recently due to its wide application backgrounds. In this paper, we consider the skyline query problem in Wireless Sensor Network with an objective to maximize the network lifetime by proposing filter-based distributed algorithms for skyline evaluation and maintenance. We also conduct preliminary experiments to evaluate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms significantly outperform existing algorithms on various datasets.
Fast spatial co-location mining without cliqueness checking
Authors: Zhongshan Lin, SeungJin Lim
Venue: CIKM
Year: 2008

In this paper, we propose a novel, spatial co-location mining algorithm which automatically generates co-located spatial features without generating any non-clique candidates at each level. Subsequently our algorithm is more efficient than other existing level-wise co-location algorithms because no cliqueness checking is performed in our algorithm. In addition, our algorithm produces a smaller number of co-location candidates than the other existing algorithms.
A novel statistical chinese language model and its application in pinyin-to-character conversion
Authors: Bo Lin, Jun Zhang
Venue: CIKM
Year: 2008

In this paper, we present a novel Chinese language model, and study its applications, in particular in Chinese pinyin-to-character conversion. In the new model, each word is associated with supporting context constructed by mining the frequent sets of nearby phrases and their distances to the word. Such information was usually overlooked in previous n-gram model and its variants. We apply the model to Chinese pinyin-to-character conversion and find that it offers a better solution to Chinese input. The model has lower perplexity in our evaluation and higher prediction accuracy than the state-of-the-art n-gram Markov model for Chinese language.
Categorizing blogger's interests based on short snippets of blog posts
Authors: Jiahui Liu, Larry Birnbaum, Bryan Pardo
Venue: CIKM
Year: 2008

Blogs have become an important medium for people to express opinions and share information on the web. Predicting the interests of bloggers can be beneficial for information retrieval and knowledge discovery in the blogosphere. In this paper, we propose a two-layer classification model to categorize the interests of bloggers based on a set of short snippets collected from their blog posts. Experiments were conducted on a list of bloggers collected from blog directories, with their snippets collected from Google Blog Search. The results show that the proposed method is robust to errors in the lower level and achieve satisfactory performance in categorizing blogger's interests.
Real-time data pre-processing technique for efficient feature extraction in large scale datasets
Authors: Ying Liu, Lucian Vlad Lita, Radu Stefan Niculescu, Kun Bai, Prasenjit Mitra, C. Lee Giles
Venue: CIKM
Year: 2008

Due to the continuous and rampant increase in the size of domain specific data sources, there is a real and sustained need for fast processing in time-sensitive applications, such as medical record information extraction at the point of care, genetic feature extraction for personalized treatment, as well as off-line knowledge discovery such as creating evidence based medicine. Since parallel multi-string matching is at the core of most data mining tasks in these applications, faster on-line matching in static and streaming data is needed to improve the overall efficiency of such knowledge discovery. To solve this data mining need not efficiently handled by traditional information extraction and retrieval techniques, we propose a Block Suffix Shifting-based approach, which is an improvement over the state of the art multi-string matching algorithms such as Aho-Corasick, Commentz-Walter, and Wu-Manber. The strength of our approach is its ability to exploit the different block structures of domain specific data for off-line and online parallel matching. Experiments on several real world datasets show how our approach translates into significant performance improvements.
Mining influential attributes that capture class and group contrast behaviour
Authors: Elsa Loekito, James Bailey
Venue: CIKM
Year: 2008

Contrast data mining is a key tool for finding differences between sets of objects, or classes, and contrast patterns are a popular method for discrimination between two classes. However, such patterns can be limited in two primary ways: i) They do not readily allow second order differentiation - i.e. discovering contrasts of contrasts, ii) Mining contrast patterns often results in an overwhelming volume of output for the user. To address these limitations, this paper proposes a method which can identify contrast behaviour across both classes and also groups of classes. Furthermore, to increase interpretability for the user, it presents a new technique for finding the attributes which represent the key underlying factors behind the contrast behaviour. The associated mining task is computationally challenging and we describe an efficient algorithm to handle it, based on binary decision diagrams. Experimental results demonstrate that our technique can efficiently identify and explain contrast behaviour which would be difficult or impossible to isolate using standard techniques.
Revisiting the relationship between document length and relevance
Authors: David E. Losada, Leif Azzopardi, Mark Baillie
Venue: CIKM
Year: 2008

The scope hypothesis in Information Retrieval (IR) states that a relationship exists between document length and relevance, such that the likelihood of relevance increases with document length. A number of empirical studies have provided statistical evidence supporting the scope hypothesis. However, these studies make the implicit assumption that modern test collections are complete (i.e. all documents are assessed for relevance). As a consequence the observed evidence is misleading. In this paper we perform a deeper analysis of document length and relevance taking into account that test collections are incomplete. We first demonstrate that previous evidence supporting the scope hypothesis was an artefact of the test collection, where there is a bias towards longer documents in the pooling process. We evaluate whether this length bias affects system comparison when using incomplete test collections. The results indicate that test collections are problematic when considering MAP as a measure of effectiveness but are relatively robust when using bpref. The implications of the study indicate that retrieval models should not be tuned to favour longer documents, and that designers of new test collections should take measures against length bias during the pooling process in order to create more reliable and robust test collections.
On low dimensional random projections and similarity search
Authors: Yu-En Lu, Pietro Liò, Steven Hand
Venue: CIKM
Year: 2008

Random projection (RP) is a common technique for dimensionality reduction under L2 norm for which many significant space embedding results have been demonstrated. However, many similarity search applications often require very low dimension embeddings in order to reduce overhead and boost performance. Inspired by the use of symmetric probability distributions in previous work, we propose a novel RP algorithm, Beta Random Projection, and give its probabilistic analyses based on Beta and Gaussian approximations. We evaluate the algorithm in terms of standard similarity metrics with other RP algorithms as well as the singular value decomposition (SVD). Our experimental results show that BRP preserves both similarity metrics well and, under various dataset types including random point sets, text (TREC5) and images, provides sharper and consistent performance.
Transaction reordering with application to synchronized scans
Authors: Gang Luo, Jeffrey F. Naughton, Curt J. Ellmann, Michael Watzke
Venue: CIKM
Year: 2008

Traditional workload management methods mainly focus on the current system status while information about the interaction between queued and running transactions is largely ignored. An exception to this is the transaction reordering method, which reorders the transaction sequence submitted to the RDBMS and improves the transaction throughput by considering both the current system status and information about the interaction between queued and running transactions. The existing transaction reordering method only considers the reordering opportunities provided by analyzing the lock conflict information among multiple transactions. This significantly limits the applicability of the transaction reordering method. In this paper, we extend the existing transaction reordering method into a general transaction reordering framework that can incorporate various factors as the reordering criteria. We show that by analyzing the resource utilization information of transactions, the transaction reordering method can also improve the system throughput by increasing the resource sharing opportunities among multiple transactions. We provide a concrete example on synchronized scans and demonstrate the advantages of our method through experiments with a commercial parallel RDBMS.
MedSearch: a specialized search engine for medical information retrieval
Authors: Gang Luo, Chunqiang Tang, Hao Yang, Xing Wei
Venue: CIKM
Year: 2008

People are thirsty for medical information. Existing Web search engines often cannot handle medical search well because they do not consider its special requirements. Often a medical information searcher is uncertain about his exact questions and unfamiliar with medical terminology. Therefore, he sometimes prefers to pose long queries, describing his symptoms and situation in plain English, and receive comprehensive, relevant information from search results. This paper presents MedSearch, a specialized medical Web search engine, to address these challenges. MedSearch uses several key techniques to improve its usability and the quality of search results. First, it accepts queries of extended length and reforms long queries into shorter queries by extracting a subset of important and representative words. This not only significantly increases the query processing speed but also improves the quality of search results. Second, it provides diversified search results. Lastly, it suggests related medical phrases to help the user quickly digest search results and refine the query. We evaluated MedSearch using medical questions posted on medical discussion forums. The results show that MedSearch can handle various medical queries effectively and efficiently.
Content-based filtering for efficient online materialized view maintenance
Authors: Gang Luo, Philip S. Yu
Venue: CIKM
Year: 2008

Real-time materialized view maintenance has become increasingly popular, especially in real-time data warehousing and data streaming environments. Upon updates to base relations, maintaining the corresponding materialized views can bring a heavy burden to the RDBMS. A traditional method to mitigate this problem is to use the where clause condition in the materialized view definition to detect whether an update to a base relation is relevant and can affect the materialized view. However, this detection method does not consider the content in the base relations and hence misses a large number of filtering opportunities. In this paper, we propose a content-based method for detecting irrelevant updates to base relations of a materialized view. At the cost of using more space, this method increases the probability of catching irrelevant updates by judiciously designing filtering relations to capture the content in the base relations. Based on the content-based method, a prototype real-time data warehouse has been implemented on top of IBM's System S using IBM DB2. Using an analytical model and our prototype, we show that the content-based method can catch most (or all) irrelevant updates to base relations that are missed by the traditional method. Thus, when the fraction of irrelevant updates is non-negligible, the load on the RDBMS due to materialized view maintenance can be significantly reduced.
Real-time new event detection for video streams
Authors: Gang Luo, Rong Yan, Philip S. Yu
Venue: CIKM
Year: 2008

Online detection of video clips that present previously unseen events in a video stream is still an open challenge to date. For this online new event detection (ONED) task, existing studies mainly focus on optimizing the detection accuracy instead of the detection efficiency. As a result, it is difficult for existing systems to detect new events in real time, especially for large-scale video collections such as the video content available on the Web. In this paper, we propose several scalable techniques to improve the video processing speed of a baseline ONED system by orders of magnitude without sacrificing much detection accuracy. First, we use text features alone to filter out most of the non-new-event clips and to skip those expensive but unnecessary steps including image feature extraction and image similarity computation. Second, we use a combination of indexing and compression methods to speed up text processing. We implemented a prototype of our optimized ONED system on top of IBM's System S. The effectiveness of our techniques is evaluated on the standard TRECVID 2005 benchmark, which demonstrates that our techniques can achieve a 480-fold speedup with detection accuracy degraded less than 5%.
Transfer learning from multiple source domains via consensus regularization
Authors: Ping Luo, Fuzhen Zhuang, Hui Xiong, Yuhong Xiong, Qing He
Venue: CIKM
Year: 2008

Recent years have witnessed an increased interest in transfer learning. Despite the vast amount of research performed in this field, there are remaining challenges in applying the knowledge learnt from multiple source domains to a target domain. First, data from multiple source domains can be semantically related, but have different distributions. It is not clear how to exploit the distribution differences among multiple source domains to boost the learning performance in a target domain. Second, many real-world applications demand this transfer learning to be performed in a distributed manner. To meet these challenges, we propose a consensus regularization framework for transfer learning from multiple source domains to a target domain. In this framework, a local classifier is trained by considering both local data available in a source domain and the prediction consensus with the classifiers from other source domains. In addition, the training algorithm can be implemented in a distributed manner, in which all the source-domains are treated as slave nodes and the target domain is used as the master node. To combine the training results from multiple source domains, it only needs share some statistical data rather than the full contents of their labeled data. This can modestly relieve the privacy concerns and avoid the need to upload all data to a central location. Finally, our experimental results show the effectiveness of our consensus regularization learning.
SoRec: social recommendation using probabilistic matrix factorization
Authors: Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King
Venue: CIKM
Year: 2008

Data sparsity, scalability and prediction quality have been recognized as the three most crucial challenges that every collaborative filtering algorithm or recommender system confronts. Many existing approaches to recommender systems can neither handle very large datasets nor easily deal with users who have made very few ratings or even none at all. Moreover, traditional recommender systems assume that all the users are independent and identically distributed; this assumption ignores the social interactions or connections among users. In view of the exponential growth of information generated by online social networks, social network analysis is becoming important for many Web applications. Following the intuition that a person's social network will affect personal behaviors on the Web, this paper proposes a factor analysis approach based on probabilistic matrix factorization to solve the data sparsity and poor prediction accuracy problems by employing both users' social network information and rating records. The complexity analysis indicates that our approach can be applied to very large datasets since it scales linearly with the number of observations, while the experimental results shows that our method performs much better than the state-of-the-art approaches, especially in the circumstance that users have made few or no ratings.