Nowadays, many online services use recommendation systems to provide personalized item recommendations to users. Collaborative filtering is the major paradigm in recommendation systems. Based on user-item interaction data, collaborative filtering recommends items to a user based on other similar users. The problem of interest disentanglement in recommendation now has attracted the attention of many researchers. Several works have proposed methods to disentangle conformity from user private interest, by assuming that conformity is correlated to item popularity. However, such modeling is simplistic and overlooks many possibilities between user public and private interest, and the item popularity. For example, a user can privately like a popular movie or buy a niche music album due to the stimulation of the social environment. In this paper, we propose a more comprehensive social behavior model that describes fine-grained relationships between user interest and item popularity. Our model does not use explicit user relationship data. Instead, we extract social behavior patterns directly from user-item interaction data. We also make our model into a recommendation framework called Disentangled Social Consumer Preference (DSCP), which can be integrated into existing recommendation models such as BPRMF. Our extensive experiments with four datasets from different services show that our model can outperform state-of-the-art baseline models. We achieve better recommendation accuracy in both the usual random test and the intervened test that shows debiasing effect.

Abstract How can we estimate the result size for a given query on complex spatial objects like polygons? Estimating a query’s result size, also known as the cardinality estimation, plays a significant role in query scheduling and optimization. Accurate and fast cardinality estimation substantially improves query efficiency. Existing compatible solutions, mainly histogram-based, deal with polygons as their minimal bounding rectangles for easier processing, which leads to inaccurate estimation. To address this issue, we present PolyCard, a learned cardinality estimator for intersection queries on spatial polygons. We successfully apply learning techniques to spatial polygons with variable sizes. PolyCard has the following properties. (i) Accurate: PolyCard improves 30% accuracy compared with existing solutions, (ii) Fast: PolyCard takes only 4 microseconds for an estimation, and (iii) Stable: PolyCard is robust against datasets and queries of different cardinalities. Our experiments on four real-world datasets of millions of polygons demonstrate the efficiency and effectiveness of PolyCard.

Abstract With the explosive growth of online information, users may also face information overload. To handle this problem, recommender systems have become an effective strategy, which can analyze the characters of users and items to provide valuable information. One of the important types of information is the item’s side information. For example, in Amazon dataset, side information mainly includes visual side information (e.g., image and video), textual side information (e.g., title and description), and auxiliary side information (e.g., brand and category). To analyze various types of side information, some research designed multiple modalities for different types of side information, which can improve the performance of the recommender system. To analyze the deeper relationships between users and items, recent works also use a graph structure to represent the interactions. Existing works on multi-modal recommender systems using graph neural networks largely depend on the interaction records, while little effort focuses on the relationships between interactions and various types of side information. In this paper, we propose a novel multi-task learning model. First, we construct the interaction records to graphs for each modality to gather the representations, and then we analyze the representations of each modality and the specific side information based on the similarities. We design a multi-task multi-modal graph neural network framework built upon message passing with the attention mechanism of graph neural networks, which can generate the representations of users and items from interaction records, and then analyze the relationships between the representations from GNNs and item’s side information. We conduct experiments on three public datasets, Amazon, Modcloth and MovieLens. The results of our model outperform the state-of-the-art methods.

In democratic countries, political interest is deeply involved in people’s daily lives. Research in political consumerism shows that product purchase decision is also influenced by the political orientation of the consumer. In traditional recommendation system design, user interest in an item is provided by a unified model. Recently, interest disentanglement methods have been introduced. It is shown that by disentangling interest factors such as conformity and private interest, recommendation performance can be significantly improved. However, few studies attempt to disentangle political interest in purchase behavior, which is bipolar. In this article, we propose a method to extract political interest model from e-commerce interaction data, which is supported by a novel word-level political bias assignment. For the bias assignment part, we improved a political bias distilling method. For the political interest model extraction part, we extend a one-side bias method to make it support bipolar bias. We compare our method with state-of-the-art baseline methods in several evaluation settings, and the experimental results show that our method can achieve superior performance. Further investigation shows that our method is consistent with theories of political consumerism.

Political polarization is commonly observed in democratic countries. While it allows individual citizens to freely choose sides, it also causes the problem of separation and isolation. Especially in information-seeking behaviors, echo chambers and filter bubbles are observed. In this article, we present a political sentiment dictionary for analyzing political polarizatio and increasing information heterogeneity. It takes advantage of large-scale social media data and is thus superior in accuracy and coverage compared to manually crafted dictionaries. Generated from Japanese tweets, more than 50k words in this dictionary cover aspects ranging from political parties and public entities to foods and personal hobbies. We describe in detail the method to construct this dictionary, which can be replicated for other languages and countries. We demonstrate the use of this dictionary in the application of recommendation diversification. We show with real-world e-commerce data that the use of the dictionary can generally increase the diversity in product recommendations, effectively mitigating the filter bubbles.

Building high-quality recommender systems is challenging for new services and small companies, because of their sparse interactions. Cross-domain recommendations (CDRs) alleviate this issue by transferring knowledge from data in external domains. However, most existing CDRs leverage data from only a single external domain and serve only two domains. CDRs serving multiple domains require domain-shared entities (i.e., users and items) to transfer knowledge, which significantly limits their applications due to the hardness and privacy concerns of finding such entities. We therefore focus on a more general scenario, non-overlapped multi-target CDRs (NO-MTCDRs), which require no domain-shared entities and serve multiple domains. Existing methods require domain-shared users to learn user preferences and cannot work on NO-MTCDRs. We hence propose MITrans, a novel mutual information-based (MI-based) preference disentangling and transferring framework to improve recommendations for all domains. MITrans effectively leverages knowledge from multiple domains as well as learning both domain-shared and domain-specific preferences without using domain-shared users. In MITrans, we devise two novel MI constraints to disentangle domain-shared and domain-specific preferences. Moreover, we introduce a module that fuses domain-shared preferences in different domains and combines them with domain-specific preferences to improve recommendations. Our experimental results on two real-world datasets demonstrate the superiority of MITrans in terms of recommendation quality and application range against state-of-the-art overlapped and non-overlapped CDRs.

Abstract Organized event is an important form of human activity. Nowadays, many digital platforms offer organized events on the Internet, allowing users to be organizers or participants. For such platforms, it is beneficial to predict potential event participants. Existing work on this problem tends to borrow recommendation techniques. However, compared to e-commerce items and purchases, events and participation are usually of a much smaller frequency, and the data may be insufficient to learn an accurate prediction model. In this paper, we propose to utilize social media retweeting activity to enhance the learning of event participant prediction models. We create a joint knowledge graph to bridge the social media and the target domain, assuming that event descriptions and tweets are written in the same language. Furthermore, we propose a learning model that utilize retweeting information for the target domain prediction more effectively. We conduct comprehensive experiments in two scenarios with real-world data. In each scenario, we set up training data of different sizes, as well as warm and cold test cases. The evaluation results show that our approach consistently outperforms several baseline models in both warm and cold tests.

Clustering multi-dimensional points is a fundamental task in many fields, and density-based clustering supports many applications because it can discover clusters of arbitrary shapes. This article addresses the problem of Density-Peaks Clustering (DPC) in Euclidean space. DPC already has many applications, but its straightforward implementation incurs O ( n 2 ) time, where n is the number of points, thereby does not scale to large datasets. To enable DPC on large datasets, we first propose empirically efficient exact DPC algorithm, Ex-DPC. Although this algorithm is much faster than the straightforward implementation, it still suffers from O ( n 2 ) time theoretically. We hence propose a new exact algorithm, Ex-DPC++, that runs in o ( n 2 ) time. We accelerate their efficiencies by leveraging multi-threading. Moreover, real-world datasets may have arbitrary updates (point insertions and deletions). It is hence important to support efficient cluster updates. To this end, we propose D-DPC for fully dynamic DPC. We conduct extensive experiments using real datasets, and our experimental results demonstrate that our algorithms are efficient and scalable.

In recent years, Point Of Interest (POI) recommendations have been actively studied because of the widespread use of location-based social network services. Out-Of-Town POI recommendation methods recommend POIs outside a user’s residence, such as travel and business trip destinations. Most existing methods require a certain number of past visit sequences at destination regions or can be used only between two specific unidirectional regions. In this study, we propose an Unvisited Out-Of-Town POI Recommendation framework (UOPR), which can recommend POIs for Out-Of-Town regions that have not yet been visited by users. In addition, UOPR can learn users’ visit patterns for multiple regions simultaneously. UOPR takes into account the fact that user’s Out-Of-Town visiting tendencies vary depending on the geographical distance from their residences. It therefore adopts an approach that calculates two scores, one determined by user’s Home-Town visiting tendencies and the other by their Out-Of-Town visiting tendencies, and uses them differently. Furthermore, we propose a mask-input learning and user-embedding creation method that enables learning with enhanced interaction between POI embeddings in an Out-Of-Town POI recommendation environment, where the data are often sparse. UOPR achieves higher recommendation accuracy than existing methods on a dataset collected on a real-world service.

We propose a novel system, called Lamps (Location-Aware Moving Top-k Pub/Sub), which continuously monitors the top-k most relevant spatio-textual objects for a large number of moving top-k spatio-textual subscriptions simultaneously. Lamps employs the concept of a safe region to monitor top-k results. However, unlike with existing works that assume static objects, top-k result updates may be triggered by newly generated objects. To continuously monitor the top-k results for massive moving subscriptions efficiently, we propose SQ-tree, a novel index based on safe regions, to filter subscriptions whose top-k results do not change. Moreover, to reduce the expensive cost of safe region re-evaluation, we develop a novel approximation technique for safe region construction. Our experimental results on real datasets show that Lamps achieves higher performance than baseline approaches.

Location-based services are becoming more involved with our daily lives, so many works have considered efficiently retrieving useful objects from spatial-keyword databases. These works are promising on the user sides, but none of them considers the service provider sides. To gain profits and enrich recommendation lists, service providers conduct market analyses and want to know potential users who may be interested in their services. In this paper, to satisfy this requirement, we propose a new query, approximate reverse top-k spatial-keyword (ART) query. Given a set O of spatial-keyword objects, a set S of users (their locations and preferable keywords), a query object q, k, and an approximation ratio ϵ, an ART query retrieves such users that q is included in their approximate top-k results among O and q. A straightforward approach to processing this query is to run a top-k spatial-keyword search for each user in S. This is clearly expensive, as the number of users is generally large. We therefore propose PART, an efficient algorithm for ART query processing. In addition, we propose B-PART, which enables the processing of multiple ART queries in a batch. We conduct extensive experiments using real datasets, and the results demonstrate the efficiencies of our algorithms.

Recommender systems nowadays are commonly used in various platforms to provide information based on user preferences. In POI recommendation, systems can generally learn the users' short-term and long-term preferences, which are based on sessions and global information. Existing systems, however, usually overlook the mid-term information, which may contain important indications of user preferences. In this work, we propose a session-based POI recommender system based on Graph Neural Network (GNN). In contrast to existing work, our model can learn short-term, long-term, and mid-term preferences at the same time. In order to learn the mid-term item representation, we construct a week graph and process it by a GAT-based graph model. We further use a gate fusion to integrate three temporal dimensions to obtain the hybrid item representation. We conduct experiments with a real-world POI visiting dataset, and the evaluation results show that our model outperforms compared state-of-art models. By adding mid-term information, the prediction accuracy can be improved by 5% compared to the best baseline.

The problem of inner product search (IPS) is important in many fields. Although maximum inner product search (MIPS) is often considered, its result is usually skewed and static. Users are hence hard to obtain diverse and/or new items by using the MIPS problem. Motivated by this, we formulate a new problem, namely the fair and independent IPS problem. Given a query, a threshold, and an output size k, this problem randomly samples k items from a set of items such that the inner product of the query and item is not less than the threshold. For each item that satisfies the threshold, this problem is fair, because the probability that such an item is outputted is equal to that for each other item. This fairness can yield diversity and novelty, but this problem faces a computational challenge. Some existing (M)IPS techniques can be employed in this problem, but they require O(n) or o(n) time, where n is the dataset size. To scale well to large datasets, we propose a simple yet efficient algorithm that runs in O(log n + k) expected time. We conduct experiments using real datasets, and the results demonstrate that our algorithm is up to 330 times faster than baselines.

Order Dependencies (ODs) have many applications, such as query optimization, data integration, and data cleaning. Although many works addressed the problem of discovering OD (and its variants), they do not consider datasets with missing values, a standard observation in real-world datasets. This paper introduces the novel notion of Embedded ODs to deal with missing values, and we propose an efficient algorithm for validating embedded ODs. We conduct experiments on real-world datasets, and the results confirm the efficiency of our algorithm.

Social media as a background information source has been utilized in many practical computational tasks, such as stock price prediction, epidemic tracking, and product recommendation. However, proper representation of an evolving social media background is still in an early research stage. In this article, we propose a representation method that considers temporal novelties as well as the fine details of word inter-dependencies. Our method is based on the tf-idf and graph embedding techniques. The proposed method has superiority over other representation methods because it takes the advantage of both the temporal aspect of tf-idf and the semantic aspect of graph embeddings. We compare our method with a variety of baselines in two practical application scenarios using real-world data. In tweet popularity prediction, our representation achieves 5.7% less error and 12.8% higher correlation compared to the best baseline. In e-commerce product recommendation, our representation achieves 17% higher hit-rate and 20% higher NDCG compared to the best baseline.

Recommender systems nowadays are commonly deployed in e-commerce platforms to help customers making purchase decisions. Dynamic recommender considers not only static user-item interaction data, but the temporal information at the time of recommendation. Previous researches have suggested to incorporate social media as the temporal information in dynamic neural recommenders after transforming them into embeddings. While such an approach can potentially improve recommendation performance, the effectiveness is difficult to explain. In this article, we propose an explainable method to integrate social media in a dynamic neural recommender. Our method applies association rule mining, which can generate human-understandable behavior patterns from social media and e-commerce platforms. With real-world social media and e-commerce data, we show that the integration can improve accuracy by up to 14% while using the same data. Moreover, we can explain the positive cases by examining relevant association rules.

The maximum inner product search (MIPS), which finds the item with the highest inner product with a given query user, is an essential problem in the recommendation field. Usually e-commerce companies face situations where they want to promote and sell new or discounted items. In these situations, we have to consider the following questions: Who is interested in the items, and how do we find them? This article answers this question by addressing a new problem called reverse maximum inner product search (reverse MIPS). Given a query vector and two sets of vectors (user vectors and item vectors), the problem of reverse MIPS finds a set of user vectors whose inner product with the query vector is the maximum among the query and item vectors. Although the importance of this problem is clear, its straightforward implementation incurs a computationally expensive cost. We therefore propose Simpfer, a simple, fast, and exact algorithm for reverse MIPS. In an offline phase, Simpfer builds a simple index that maintains a lower bound of the maximum inner product. By exploiting this index, Simpfer judges whether the query vector can have the maximum inner product or not, for a given user vector, in a constant time. Our index enables filtering user vectors, which cannot have the maximum inner product with the query vector, in a batch. We theoretically demonstrate that Simpfer outperforms baselines employing state-of-the-art MIPS techniques. In addition, we answer two new research questions. Can approximation algorithms further improve reverse MIPS processing? Is there an exact algorithm that is faster than Simpfer? For the former, we show that approximation with quality guarantee provides a little speed-up. For the latter, we propose Simpfer++, a theoretically and practically faster algorithm than Simpfer. Our extensive experiments on real datasets show that Simpfer is at least two orders of magnitude faster than the baselines, and Simpfer++ further improves the online processing time.

Deep learning-based recommender systems may lead to over-fitting when lacking training interaction data. This over-fitting significantly degrades recommendation performances. To address this data sparsity problem, cross-domain recommender systems (CDRSs) exploit the data from an auxiliary source domain to facilitate the recommendation on the sparse target domain. Most existing CDRSs rely on overlapping users or items to connect domains and transfer knowledge. However, matching users is an arduous task and may involve privacy issues when data comes from different companies, resulting in a limited application for the above CDRSs. Some studies develop CDRSs that require no overlapping users and items by transferring learned user interaction patterns. However, they ignore the bias in user interaction patterns between domains and hence suffer from an inferior performance compared with single-domain recommender systems. In this paper, based on the above findings, we propose a novel CDRS, namely semantic clustering enhanced debiasing graph neural recommender system (SCDGN), that requires no overlapping users and items and can handle the domain bias. More precisely, SCDGN semantically clusters items from both domains and constructs a cross-domain bipartite graph generated from item clusters and users. Then, the knowledge is transferred via this cross-domain user-cluster graph from source to the target. Furthermore, we design a debiasing graph convolutional layer for SCDGN to extract unbiased structural knowledge from the cross-domain user-cluster graph. Our Experimental results on three public datasets and a pair of proprietary datasets verify the effectiveness of SCDGN over stateof-the-art models in terms of cross-domain recommendations.

Spatial data analysis is a classic yet important topic because of its wide range of applications. Recently, as a spatial data analysis approach, a neighbor graph of a set P of spatial points has often been employed. This paper also considers a spatial neighbor graph and addresses a new problem, namely top-N weighted spatial k-clique retrieval. This problem searches for the N minimum weighted cliques consisting of k points in P, and it has important applications, such as community detection and co-location pattern mining. Recent spatial datasets have many points, and efficiently dealing with such big datasets is one of the main requirements of applications. A straightforward approach to solving our problem is to try to enumerate all k-cliques, which incurs O(nkk2) time. Since k ≥ 3, this approach cannot achieve the main requirement, so computing the result without enumerating unnecessary k-cliques is required. This paper achieves this challenging task and proposes a simple practically-efficient algorithm that returns the exact answer. We conduct experiments using two real spatial datasets consisting of million points, and the results show the efficiency of our algorithm, e.g., it can return the exact top-N result within 1 second when N ≤ 1000 and k ≤ 7.

Big data mining is well known to be an important task for data science, because it can provide useful observations and new knowledge hidden in given large datasets. Proximity-based data analysis is particularly utilized in many real-life applications. In such analysis, the distances to k nearest neighbors are usually employed, thus its main bottleneck is derived from data retrieval. Much efforts have been made to improve the efficiency of these analyses. However, they still incur large costs, because they essentially need many data accesses. To avoid this issue, we propose a machine-learning technique that quickly and accurately estimates the k-NN distances (i.e., distances to the k nearest neighbors) of a given query. We train a fully connected neural network model and utilize pivots to achieve accurate estimation. Our model is designed to have useful advantages: it infers distances to the k-NNs at a time, its inference time is O(1) (no data accesses are incurred), but it keeps high accuracy. Our experimental results and case studies on real datasets demonstrate the efficiency and effectiveness of our solution.

Maximum inner product search (or k-MIPS) is a fundamental operation in recommender systems that infer preferable items for users. To support large-scale recommender systems, existing studies designed scalable k-MIPS algorithms. However, these studies do not consider diversity, although recommending diverse items is important to improve user satisfaction. We therefore formulate a new problem, namely diversity-aware k-MIPS. In this problem, users can control the degree of diversity in their recommendation lists through a parameter. However, exactly solving this problem is unfortunately NP-hard, so it is challenging to devise an efficient, effective, and practical algorithm for the diversity-aware k-MIPS problem. This paper overcomes this challenge and proposes IP-Greedy, which incorporates new early termination and skipping techniques into a greedy algorithm. We conduct extensive experiments on real datasets, and the results demonstrate the efficiency and effectiveness of our algorithm. Also, we conduct a case study of the diversity-aware k-MIPS problem on a real dataset. We confirm that this problem can make recommendation lists diverse while preserving high inner products of user and item vectors in the lists.

Huge amounts of spatio-textual objects, such as geo-tagged tweets, are being generated at an unprecedented scale, leading to a variety of applications such as location-based recommendation and sponsored search. Many of these applications need to support moving top-k spatio-textual subscriptions. For example, while walking, a tourist issues a moving subscription and looks for top-k advertisements published by nearby shops. Unfortunately, existing methods that monitor the results of spatio-textual subscriptions support only static top-k subscriptions or moving boolean subscriptions. In this article, we propose a novel system, called Lamps (Location-Aware Moving Top-k Pub/Sub), which continuously monitors the top-k most relevant spatio-textual objects for a large number of moving top-k spatio-textual subscriptions simultaneously. To the best of our knowledge, this is the first study of a location-aware moving top-k pub/sub system. As with existing works on continuous moving top-k subscription processing, Lamps employs the concept of a safe region to monitor top-k results. However, unlike with existing works that assume static objects, top-k result updates may be triggered by newly generated objects. To continuously monitor the top-k results for massive moving subscriptions efficiently, we propose SQ-tree, a novel index based on safe regions, to filter subscriptions whose top-k results do not change. Moreover, to reduce the expensive cost of safe region re-evaluation, we develop a novel approximation technique for safe region construction. Our experimental results on real datasets show that Lamps achieves higher performance than baseline approaches.

Abstract In many fields, e.g., data mining and machine learning, distance-based outlier detection (DOD) is widely employed to remove noises and find abnormal phenomena, because DOD is unsupervised, can be employed in any metric spaces, and does not have any assumptions of data distributions. Nowadays, data mining and machine learning applications face the challenge of dealing with large datasets, which requires efficient DOD algorithms. We address the DOD problem with two different definitions. Our new idea, which solves the problems, is to exploit an in-memory proximity graph. For each problem, we propose a new algorithm that exploits a proximity graph and analyze an appropriate type of proximity graph for the algorithm. Our empirical study using real datasets confirms that our DOD algorithms are significantly faster than state-of-the-art ones.

This paper addresses the problem of top-k inner product join, which, given two sets of high-dimensional vectors and a result size k, outputs k pairs of vectors that have the largest inner product. This problem has important applications, such as recommendation, information extraction, and finding outlier correlation. Unfortunately, computing the exact answer incurs an expensive cost for large high-dimensional datasets. We therefore consider an approximate solution framework that efficiently retrieves k pairs of vectors with large inner products. To exploit this framework and obtain an accurate answer, we extend a state-of-the-art proximity graph for inner product search. We conduct experiments on real datasets, and the results show that our solution is faster and more accurate than baselines with state-of-the-art techniques.

Due to the proliferation of GPS-enabled mobile devices and IoT environments, location-based services are generating a large number of objects that contain both spatial and keyword information, and spatial-keyword databases are receiving much attention. This paper addresses the problem of top-k spatial-keyword similarity join, which outputs k object pairs with the highest similarity. This query is a primitive operator for important applications, including duplicate detection, recommendation, and clustering.

The MIPS (maximum inner product search), which finds the item with the highest inner product with a given query user, is an essential problem in the recommendation field. It is usual that e-commerce companies face situations where they want to promote and sell new or discounted items. In these situations, we have to consider a question: who are interested in the items and how to find them? This paper answers this question by addressing a new problem called reverse maximum inner product search (reverse MIPS). Given a query vector and two sets of vectors (user vectors and item vectors), the problem of reverse MIPS finds a set of user vectors whose inner product with the query vector is the maximum among the query and item vectors. Although the importance of this problem is clear, its straightforward implementation incurs a computationally expensive cost.

Clustering multi-dimensional points is a fundamental task in many fields, and density-based clustering supports many applications as it can discover clusters of arbitrary shapes. This paper addresses the problem of Density-Peaks Clustering (DPC), a recently proposed density-based clustering framework. Although DPC already has many applications, its straightforward implementation incurs a quadratic time computation to the number of points in a given dataset, thereby does not scale to large datasets.

Distance-based outlier detection is widely adopted in many fields, e.g., data mining and machine learning, because it is unsupervised, can be employed in a generic metric space, and does not have any assumptions of data distributions. Data mining and machine learning applications face a challenge of dealing with large datasets, which requires efficient distance-based outlier detection algorithms. Due to the popularization of computational environments with large memory, it is possible to build a main-memory index and detect outliers based on it, which is a promising solution for fast distance-based outlier detection.

Recent applications employ publish/subscribe (Pub/Sub) systems so that publishers can easily receive attentions of customers and subscribers can monitor useful information generated by publishers. Due to the prevalence of smart devices and social networking services, a large number of objects that contain both spatial and keyword information have been generated continuously, and the number of subscribers also continues to increase. This poses a challenge to Pub/Sub systems: they need to continuously extract useful information from massive objects for each subscriber in real time.

Nowadays, advertising (ad) deliveries are conducted in a targeted manner to improve their effectiveness and efficiency. However, human behavior data in ad-platforms such as Web browsing history is complex and contains a lot of “noise”. On the other hand, information in the advertiser's domain (e.g. e-commerce sites) seems to contain less noise (e.g. product browsing history) with respect to ad-targeting. We introduce a new denoising method for behavioral ad-targeting based on the idea of feature distribution alignment induced by the advertiser's domain. This denoised distribution induction can be achieved by employing domain adversarial training with stabilization techniques. We evaluate our model on real world data originating from an e-commerce site and an ad-platform. The results of an ablation study have demonstrated the advantage of utilizing an advertiser's domain for denoising human behavior data of an ad-platform domain.

This paper investigates a new query, called an MIO query, that retrieves the Most Interactive Object in a given spatial dataset. Consider that an object consists of many spatial points. Given a distance threshold, we say that two objects interact with each other if they have a pair of points whose distance is within the threshold. An MIO query outputs the object that interacts with other objects the most, and it is useful for analytical applications e.g., neuroscience and trajectory databases. The MIO query processing problem is challenging: a nested loop algorithm is computationally inefficient and a theoretical algorithm is computationally efficient but incurs a quadratic space cost. Our solution efficiently processes MIO queries with a novel index, BIGrid (a hybrid index of compressed Bitset, Inverted list, and spatial Grid structures), with a practical memory cost. Furthermore, our solution is designed so that previous query results and multi-core environments can be exploited to accelerate query processing efficiency. Our experiments on synthetic and real datasets demonstrate the efficiency of our solution.

In many applications, data objects can be represented as sets. For example, in video on-demand and social network services, the user data consists of a set of movies that have been watched and a set of users (friends), respectively, and they can be used for recommendation and information extraction. The problem of set similarity self-join hence has been studied extensively. Existing studies assume that sets are static, but in the above applications, sets are dynamically updated, and this requires continuous updating the join result. In this paper, we study a novel problem, dynamic set kNN self-join, i.e., for each set, we continuously compute its k nearest neighbor sets. Our problem poses a challenge for the efficiency of computation, because just an element insertion (deletion) into (from) a set may affect the kNN results of many sets. To address this challenge, we first investigate the property of the dynamic set kNN self-join problem to observe the search space derived from a set update. Then, based on this observation, we propose an efficient algorithm. This algorithm employs an indexing technique that enables incremental similarity computation and prunes unnecessary similarity computation. Our empirical studies using real datasets show the efficiency and scalability of our algorithm.

Behavioral targeting (BT) is an important function for a company to reach a wide range of potential users. Trans-domain BT which targets potential users of one (source) domain (e.g. E-Commerce) who lie in another (target) domain (e.g. Ad Network) is a promising method to expand the range. However, it is difficult for trans-domain BT to keep its targeting quality high in case when ID linkage across domains is limited. To realize high quality trans-domain BT with limited ID linkage, we propose a method to cross-connect private touchpoints to users in each domain, which we call Virtual Touch-Point (VTP). Here, we utilize transfer learning to acquire knowledge to tie two domains. We made a VTP prototype by implementing typical transfer learning algorithms and evaluated its effectiveness using real-world data of two domains: (source) E-Commerce → (target) Ad Network.

We study the novel problem of continuous mining of top-k closed co-occurrence patterns across multiple streams. We employ sliding window setting in this problem, and each pattern is ranked based on count, which is the number of streams that have generated the pattern. Since objects are consecutively generated and deleted, the count of a given pattern is dynamic, which may change the rank of the pattern. This renders a challenge to monitoring the top-k answer in real-time. We propose an index-based algorithm that addresses the challenge and provides the exact answer. Specifically, we propose the CP-Graph, a hybrid index of graph and inverted file structures. The CP-Graph can efficiently compute the count of a given pattern and update the answer while pruning unnecessary patterns. Our experimental study on real datasets demonstrates the efficiency and scalability of our solution.

In this paper, we propose a method that fully combines top-k query processing with replication strategy in mobile ad hoc networks (MANETs). The goal is to acquire perfect accuracy of query results with a minimal overhead and delay. Currently, no replication strategy achieves efficient allocation of replicas for top-k queries, and no top-k query processing guarantees perfect accuracy of query results in MANETs. We propose a new replication strategy FReT (topology-Free Replication for Top-k query) and new top-k query processing methods. FReT advantages efficient top-k query processing from limited search area even if mobile nodes move. In our top-k query processing method, the search area gradually increases until receiving an exact answer. We demonstrate, through extensive simulations, that our approaches function well in terms of small delay and overhead.

A top-k dominating query returns k data objects that dominate the highest number of data objects in a given dataset. This query provides us with a set of intuitively preferred data, thus can support a wide variety of multi-criteria decision-making applications, e.g., e-commerce and web search. Due to the growth of data centers and cloud computing infrastructures, the above applications are increasingly being operated in distributed environments. These motivate us to address the problem of distributed top-k dominating query processing. We propose an efficient decentralized algorithm that exploits virtual points and returns the exact answer. The virtual points are utilized to focus on the data space to be preferentially searched and also to limit the search space to prune unnecessary computation and data forwarding. We also propose two other algorithms, which return an approximate answer set while further reducing query processing time. Extensive experiments on both real and synthetic data demonstrate the efficiency and scalability of our algorithms.

Due to recent developments in sensor technologies, mobile sensor device use has become widespread, and many researchers have been attempting to leverage data collected by these devices. We call such data `mobile sensor data'; and environments where mobile sensor data arrive continuously, `mobile sensor stream' environments. Mobile sensor data are geo-referenced data with environmental attribute values; and they enable us to determine the geographical distribution of hot spots by retrieving data with comparatively extreme environmental attribute values (such as higher air-pollution index values). Top-k search result diversification in geographical space is valid for applications of this sort. By monitoring a diversified set over mobile sensor streams, we can trace changes in the distribution of hot spots. However, the computation costs for maintaining such diversified sets are high when we have to monitor a large amount of mobile sensor data. Thus, in this paper, we propose an efficient diversified set monitoring method for mobile sensor stream environments. Our proposed method can reduce the amount of examined data by exploiting our proposed regular grid-based data structure, and the diversified set can thereby be maintained much more efficiently. Our experimental results confirm that the proposed method involves much shorter computation time in comparison with the baseline method.

In this paper, we present results of investigation on the dynamics of group decision making - how people discuss and make a decision-with collaborative web search. Prior works proposed systems that support group decision making with web search but have not examined the influence of discussion behaviors especially on the satisfaction levels with the final conclusion. In this study, we conducted a set of experiments to observe discussion behaviors and the consequent satisfaction with the conclusion using our experimental system and a set of questionnaires. The task for each participant was to make a decision on a restaurant. Our primary results revealed (1) the similar activities across all groups at the beginning and the end of the group discussion, (2) a lack of correspondence between the satisfaction with the conclusion and the time spent to reach the conclusion, and (3) the presumption that a member who actively engaged in the activities that were visible for the other members was likely to be voted as a leader in the group discussion beyond the discussion. Finally, we discussed how to implement intelligent systems that aid group decision making.

The recent Bigdata and IoTera has presented a number of applications that generate objects in a streaming fashion. It is well-known that real-time mining of important patterns from data streams support many domains. In retail markets and social network services, for example, such patterns are itemsets and words that frequently appear in many user-accounts, i.e., co-occurrence patterns. To efficiently monitor co-occurrence patterns, we address the novel problem of mining top-k closed co-occurrence patterns across multiple streams. We employ sliding window setting in this problem, and each pattern is ranked based on count, which is the number of streams that have generated the pattern. Since objects are consecutively generated and deleted, the count of a given pattern is dynamic, which may change the rank of the pattern. This renders a challenge to monitoring the top-k answer in real-time. We propose an index-based algorithm that addresses the challenge and provides the exact answer. Specifically, we propose the CP-Graph, a hybrid index of graph and inverted file structures. The CP-Graph can efficiently compute the count of a given pattern and update the answer while pruning unnecessary patterns. Our experimental study on real datasets demonstrates the efficiency and scalability of our solution.

Inverse Document Frequency (IDF) is widely accepted term weighting scheme whose robustness is supported by many theoretical justifications. However, applying IDF to word N-grams (or simply N-grams) of any length without relying on heuristics has remained a challenging issue. This article describes a theoretical extension of IDF to handle N-grams. First, we elucidate the theoretical relationship between IDF and information distance, a universal metric defined by the Kolmogorov complexity. Based on our understanding of this relationship, we propose N-gram IDF, a new IDF family that gives fair weights to words and phrases of any length. Based only on the magnitude relation of N-gram IDF weights, dominant N-grams among overlapping N-grams can be determined. We also propose an efficient method to compute the N-gram IDF weights of all N-grams by leveraging the enhanced suffix array and wavelet tree. Because the exact computation of N-gram IDF provably requires significant computational cost, we modify it to a fast approximation method that can estimate weight errors analytically and maintain application-level performance. Empirical evaluations with unsupervised/supervised key term extraction and web search query segmentation with various experimental settings demonstrate the robustness and language-independent nature of the proposed N-gram IDF.

Recently, IoT (Internet of Things) environments have begun to attract a great deal of attention. In IoT environments, various “things”, such as sensors, are connected to the Internet and act as distributed data sources to continuously generate big data (stream data). One of the main research issues for such stream data is fast execution of continuous queries. Most conventional schemes assume that processing servers receive data streams from remote data sources. Therefore, when large numbers of data sources are distributed in IoT environments, large amounts of communications traffic from those data sources are produced. This is the main cause of long stream processing times. To tackle this key problem, we take this feature of IoT environments into account and try to reduce the stream processing time by reducing the stream processing load. Our proposed scheme extracts conditional expressions, and determines the order of evaluation of these expressions, in order to reduce processing and communication loads. Our evaluation shows that the proposed scheme can reduce the maximum number of communication hops and the average amount of communication traffic in IoT environments.

Due to the increase of GPS enabled devices and a lot of locationbased services, spatial objects are continuously generated. This paper addresses a problem of monitoring MaxRS (Maximizing Range Sum) in spatial data streams. Given a set of weighted spatial (2dimensional) objects, this problem is to monitor a location of a given user-specified sized rectangle where the sum of the weights of the objects covered by the rectangle is maximized. Many real life applications obtain a benefit from monitoring MaxRS, e.g., traffic analysis and event detection in urban sensing, but this problem has not yet been addressed so far. Although some algorithms for static objects have been proposed, executing such an algorithm whenever new objects are generated is computationally expensive. These motivate us to develop an efficient algorithm that can monitor MaxRS efficiently. In this paper, we first design a basic algorithm that is based on an index framework and incrementally updates the result. We then enhance the algorithm and show that the enhanced algorithm can deal with error-guaranteed approximation and monitoring top-k MaxRS. Our experimental results confirm the efficiency of our approach.

Location-based service (LBS) is a typical application for mobile ad hoc networks (MANETs). In an LBS, it is effective for nodes to acquire data using convex hull queries, which retrieve the information necessary for calculating the convex hull of all nodes composing a given network. In a naive approach, the query-issuing node can determine the convex hull of the network by flooding a query throughout the entire network and receiving location information on all the nodes, but this involves excessive traffic. In addition, since the network topology changes dynamically, due to the movement of nodes, the set of vertices of the convex hull changes. Therefore, the query-issuing node must determine the convex hull in a short period of time. In this paper, we propose convex hull query processing methods for reducing traffic and response time while maintaining high accuracy of the query result in MANETs. In these methods, nodes reply with information on nodes which are convex hull vertices. In the Local Convex Hull (LCH) method, nodes reply with information on nodes which are vertices of the local convex hull, which is the convex hull composed of nodes whose information has already been received. In the Local Wrapping (LW) method, the query is transmitted only to nodes on the outer boundary. Experimental results show that our proposed methods reduce traffic and achieve short response time and high accuracy of the query result, in comparison with a naive method.

As we are in the big data era, techniques for retrieving only user-desirable data objects from massive and diverse datasets is being required. Ranking queries, e.g., top-k queries, which rank data objects based on a user-specified scoring function, enable to find such interesting data for users, and have received significant attention due to its wide range of applications. While many techniques for both centralized and distributed top-k query processing have been developed, they do not consider query keywords, i.e., simply retrieving k data with the best score. Utilizing keywords, on the other hand, is a common approach in data (and information) retrieval. Despite of this fact, there is no study on retrieving top-k data containing all query keywords. We define, in this paper, a new query which enriches the conventional top-k queries, and propose some algorithms to solve the novel problem of how to efficiently retrieve k data objects with the best score and all query from distributed databases. Extensive experiments on both real and synthetic data have demonstrated the efficiency and scalability of our algorithms in terms of communication cost and running time.

This paper first reveals the relationship between Inverse Document Frequency (IDF), a global term weighting scheme, and information distance, a universal metric defined by Kolmogorov complexity. We concretely give a theoretical explanation that the IDF of a term is equal to the distance between the term and the empty string in the space of information distance in which the Kolmogorov complexity is approximated using Web documents and the Shannon-Fano coding. Based on our findings, we propose N-gram IDF, a theoretical extension of IDF for handling words and phrases of any length. By comparing weights among N-grams of any N, N-gram IDF enables us to determine dominant N-grams among overlapping ones and extract key terms of any length from texts without using any NLP techniques. To efficiently compute the weight for all possible N-grams, we adopt two string processing techniques, i.e., maximal substring extraction using enhanced suffix array and document listing using wavelet tree. We conducted experiments on key term extraction and Web search query segmentation, and found that N-gram IDF was competitive with state-of-the-art methods that were designed for each application using additional resources and efforts. The results exemplified the potential of N-gram IDF.

In dense mobile wireless sensor networks, it is desirable to gather sensor data with as low traffic as possible. When an application requires geographical boundaries of sensor readings, it is able to satisfy the requirement while reducing traffic by gathering sensor data only from nodes located close to the boundaries. In order to do so, it is necessary to detect nodes located close to the boundaries (boundary detection). Until now, many boundary detection methods have been proposed, assuming networks constructed by fixed nodes. In these methods, each node preliminarily recognizes locations of itself and all its neighboring nodes. When applying this approach to a dense and mobile environment, it takes a large amount of traffic for exchanging information on locations of nodes. In this paper, we propose an efficient boundary detection method in dense mobile wireless sensor networks, which makes use of overhearing sensor data. In our proposed method, each node determines whether it exists close to a boundary or not based on sensor data overheard from its neighboring nodes. When a node determines that it dose not exist close to the boundary, it stops transmitting its own sensor data. By doing so, traffic for boundary detection can be reduced. We confirmed the effectiveness of our proposed method through simulation experiments.

Location-based services (LBSs) are important applications for mobile users. We consider an application in which the source node periodically disseminates location-based information in mobile ad hoc networks (MANETs). We define beneficial information as that which may be of benefit to mobile users planning to pass near the location related to the information. However, typically, mobile users change their route or travel direction when the mobile node receives beneficial information such as traffic jam and accident information (we call these information the negative location-based information). Thus, a significant problem lies in determining the proper target area for the dissemination of such information in dynamic networks because the source node is difficult to effectively know where to disseminate it. In this paper, we propose a novel location-based information dissemination method in MANETs by use of some fixed nodes. Our proposed method requires neither a positioning system, nor previous knowledge, to efficiently disseminate the information. However, the fixed nodes autonomously expand the relevant dissemination area. Through simulation experiments, we confirm that the proposed method suppresses ineffectual overhead, and that mobile users can efficiently and early receive the beneficial information.

In mobile ad hoc networks (MANETs), it is effective for mobile nodes to retrieve data items using top-k queries, in which data items are ordered according to a particular attribute score, and the query-issuing node acquires the data items with the k highest scores. However, accurate results may not be acquired in environments where malicious nodes are present. In top-k queries, it is important to neutralize attacks in which malicious nodes attempt to replace necessary data items with unnecessary ones (we call these, data replacement attacks). In this paper, we propose methods for top-k query processing and malicious node identification against data replacement attack in MANETs. In the top-k query processing method, in order to maintain accuracy of the query result, nodes reply with data items with the k highest scores, along multiple routes. Moreover, to enable detection of data replacement attacks, reply messages include information on the route along which reply messages are forwarded, and thus the query-issuing node can know the data items that properly belong to the message. In the malicious node identification method, the query-issuing node first narrows down the malicious node candidates, using the received message information, and then requests information on the data items sent by these candidates. In this way, the query-issuing node can identify the malicious node. Finally, we verify, through simulation experiments, that the proposed top-k query processing method achieves high accuracy of the query result, and that the malicious node identification method effectively identifies a malicious node.

With the increase of data generation in distributed fashions such as peer-to-peer systems and sensor networks, top-k query processing which returns only a small set of data that satisfies many users' preferences, becomes a substantial issue. When data are periodically updated in each epoch e.g., weather information, without any techniques, a naive solution is to aggregate all data and their updates to ensure the correctness of final answers, however, it is too costly in terms of data transfer especially for data aggregator nodes. In this paper, we propose a top-k monitoring query processing method in 2-tier distributed systems based on a publish-subscribe scheme. A set of top-k subscriptions specifying summary scope of users' interests is informed to aggregators to limit the number of transferred data records for each epoch. In addition, instead of issuing subscriptions of all queries, our method identifies a small set of minimal subscriptions resulting in lower communication overhead. Our experiments show that our technique is efficient and outperforms other comparative reactive methods.

In this demonstration, we introduce MLJ (MultiLingual Journalism, http://mljournalism.com), a first Web-based system that enables users to search any topic of latest tweets posted by media outlets and journalists beyond languages. Handling multilingual tweets in real time involves many technical challenges: language barrier, sparsity of words, and real-time data stream. To overcome the language barrier and the sparsity of words, MLJ harnesses CL-ESA, a Wikipedia-based language-independent method to generate a vector of Wikipedia pages (entities) from an input text. To continuously deal with tweet stream, we propose one-pass DP-means, an online clustering method based on DP-means. Given a new tweet as an input, MLJ generates a vector using CL-ESA and classifies it into one of clusters using one-pass DP-means. By interpreting a search query as a vector, users can instantly search clusters containing latest related tweets from the query without being aware of language differences. MLJ as of March 2014 supports nine languages including English, Japanese, Korean, Spanish, Portuguese, German, French, Italian, and Arabic covering 24 countries.

This paper describes a novel probabilistic method of measuring semantic similarity for real-world noisy short texts like microblog posts. Our method adds related Wikipedia entities to a short text as its semantic representation and uses the vector of entities for computing semantic similarity. Adding related entities to texts is generally a compound problem that involves the extraction of key terms, finding related entities for each key term, and the aggregation of related entities. Explicit Semantic Analysis (ESA), a popular Wikipedia-based method, solves these problems by summing the weighted vectors of related entities. However, this heuristic weighting highly depends on the rule of majority decision and is not suited to short texts that contain few key terms but many noisy terms. The proposed probabilistic method synthesizes these procedures by extending naive Bayes and achieves robust estimates of related Wikipedia entities for short texts. Experimental results on short text clustering using Twitter data indicated that our method outperformed ESA for short texts containing noisy terms.

In mobile ad hoc networks (MANETs), to acquire only necessary data items, it is effective for each mobile node to retrieve data items using a top-k query. In our previous work, we proposed a routing method for top-k query processing to reduce traffic while keeping highly accurate query result by using a routing table. This method performs query transmission by unicast to each node which contributes to collect the data items with k-highest scores. However, in highly dynamic networks, the accuracy of query result decreases because its query transmission approach makes only single route to each data item. To solve this problem, we extend the previous method in order to achieve robust routing. In our proposed method of this paper, each node does not unicast a query message, but multicasts the query message to the nodes in its routing table. This method makes multipath transmission of query messages, so that prevents from decreasing of the accuracy of the query result in highly dynamic networks. The simulation results show that our proposed method outperforms our previous method as to accuracy of the query result.

Vehicular ad hoc networks (VANETs) have been attracting increasing research interests for the past decade. To address the routing problem, many protocols have been proposed in the past several years. Routing protocols for VANETs, mostly based on the ideas of “Geographical Routing” (or geo-routing for short), typically have nodes periodically broadcast one-hop beacon messages to reveal their positions to neighbors. Nevertheless, packet loss and thus deterioration of routing performance in these protocols are anticipated in urban areas due to high density of vehicles in the network. In this paper, we propose two new VANET routing protocols, namely, Routing Protocol with Beacon Control (RPBC) and Routing Protocol with BeaconLess (RPBL), to alleviate packet losses. In RPBC, each vehicle determines whether to transmit a beacon message based on a new beacon control scheme proposed in this paper, which by minimizing redundant beacon messages reduces transmission overhead significantly. On the other hand, RPBL is a beaconless protocol where a node broadcasts a packet to its neighboring nodes and transmits packet via multiple paths to achieve high delivery ratio. Moreover, as packets in geo-routing protocols include the location of the sender, it can be used for routing without heavily relying on beacons. Accordingly, we propose the idea of virtual beacons and use it to further improve our proposed protocols. We conduct comprehensive experiments by simulation to validate our ideas and evaluate the proposed protocols. The simulation results show that our proposals can achieve high delivery ratios, short delays, and small overhead.

A variety of services utilizing users' positions have become available because of rapid advances in Global Positioning System (GPS) technologies. Since location information may reveal private information, preserving location privacy has become a significant issue. We proposed a dummy-based method of anonymizing location to protect this privacy in our previous work that generated dummies based on various restrictions in a real environment. However, the previous work assumed a simplified mobility model in which users kept moving and did not stop. If we assume a more realistic mobility model in which users often pause to visit various attractions, it becomes increasingly more difficult to generate dummies that will move naturally. In this paper, we assumed that the users' movements are known in advance and propose a dummy-based anonymization method based on user movements, where dummies move naturally while stopping at several locations. We simulated user movements on real map information and verified the method we propose was more effective than the previous one.

Caching is a common technique to improve efficiency of data access in MANETs (Mobile Ad hoc Networks), where users communicate using small portable devices connected by resource constraint wireless networks. In some MANET applications, controlling/reducing the cache locations are desirable due to security issues, restricted shared memory and maintenance cost. However, reducing the number of caches should be done by finding optimized cache locations (at highly connected and centrally located nodes) so that it does not affect the performance efficacy of data access in terms of response time. Existing cooperative caching approaches are deficient in finding such optimized cache locations as they do not focus on reducing the number of copies by finding their optimized locations to be shared among nodes. In this paper, we design and evaluate such a caching scheme using a single broker based MANET architecture to improve data access latency. Our scheme reduces the number of caches by efficiently placing them at locations which brings distant data closer to the source. The performance comparison of our scheme with one such recent caching scheme showcases improvement in data access efficiency by 30% along with reduction in number of cache locations by 72%. We evaluated data access efficiency using average hops and average roundtrip delay.

Map-based application is one of the most popular applications using a built-in GPS receiver. Users often use applications based on geographic information in situations where they share the same information needs with friends or families and conduct some tasks together. However, it is difficult to communicate geographic information with each other because existing map-based applications are basically designed for solitary work. In this paper, to support collaborative work using map-based applications, we explore important factors for collaborative use of map interface. We conducted a user experiment using a map-based application implemented with some functions for supporting collaborative work. The result shows that it is important to i) enable users to share information among multiple devices and view it individually on their own displays when they use a map together, and ii) synchronize users' displays and map operations when they communicate geographic information with each other.

In mobile ad hoc networks (MANETs), location based service (LBS) is a typical application. In a LBS, it is effective for each node to acquire data using a k Nearest Neighbor (kNN) query, which retrieves the information on the nearest k nodes from the location specified by the query. However, existing methods for kNN query processing in wired networks and wireless sensor networks cannot be applied in MANETs dueto the movement of mobile nodes. In this paper, we propose the Explosion (EXP) method, which is a kNN query processing method for reducing traffic and also keeping high accuracy of the query result in MANETs. An experimental result shows that our proposed method reduces traffic and achieves high accuracy of the query result compared with a naive method.

In this paper, we propose a method which acquires related words (entities) from multiple words by naturally disambiguating their meaning and considering their contexts. In addition, we introduce a bootstrapping method for improving the coverage of association relations. Experimental result shows that our method can acquire related words depending on the contexts of multiple words compared to the ESA-based method.

Recent mobile devices are mostly equipped with a GPS receiver. This trend has arisen a variety of location based services (LBSs) which enable users to search local information of their current locations. To use LBSs, a user needs to send his/her location information to a service provider. Users' location information is inherently private, since it can reveal the critical information. In this paper, we propose a method to protect the user's location privacy by sending the user's location with dummy locations, which are determined based on the user's current location. We conduct an experiment to evaluate the effectiveness of our proposed method using real users' trajectories on a real map.

In a mobile ad hoc network (MANET), mobile hosts basically run with battery and their battery capacity is limited. Data transmissions are one of the main factors of the power consumption of mobile hosts. Therefore energy efficient data access is one of the most important research issues in MANETs. In this paper, we introduce our recent work addressing issues of energy efficient data access in MANETs. We first present data access and replication methods that take into account the remaining amount of the battery of each host. We then present a message processing method for top-k queries in MANETs, which is effective to reduce the amount of data volume transmitted.

Cellular phones are widely used to access the Web, however, it is inconvenient to browse large-sized pages designed for desktop PCs. Since cellular phones display only small part of a Web page, users easily get lost within the page while scrolling around. Even though pages are well structured by nature, users cannot recognize it because visible portion is strictly limited. To smartly browse pages using cellular phones, navigation is essential. In this paper, we propose a novel Web browser that models browsing as motoring cities, by setting routes on Web pages and presenting traffic signs to navigate users. Users can follow routes by auto-scrolling without burdensome operations.

In ad hoc networks, to acquire only necessary data items, it is effective that each mobile node retrieves data items using a top-k query, in which data items are ordered by the score of a particular attribute, and the query-issuing mobile node acquires data items with the k highest scores. In this paper, we propose a message processing method for a top-k query for reducing traffic and keeping the accuracy of the query result, i.e., guaranteeing that data items with the k highest scores in the entire network are acquired. When a mobile node transmits query and reply messages, our method can be used to reduce candidates of data items included in the top-k result to prevent unnecessary data transmissions. Moreover, if a mobile node detects a disconnection of a radio link, it searches for an alternative path to transmit the reply message to the query-issuing node. We present simulation results to evaluate the performance of our proposed method.

In this paper, we present the results of performance evaluation of our energy-efficient data transmission reduction method in wireless sensor networks (WSNs). In our method, each node in a WSN autonomously determines whether its own reading is redundant or not by using the overheard packets transmitted by its neighbors. The redundancy of a reading is evaluated by a simple spatial interpolation using the readings of its neighbors. If the reading is determined as redundant, the node stops transmitting it. Since our method may be affected by packet losses, we conduct simulation experiments with a practical model of lossy links. The results show that our method suppresses data transmissions and reduces total energy consumption even in a lossy environment.

This paper introduces a sensor network testbed, X-sensor, that integrates multiple sensor networks deployed at different sites. X-sensor provides three functionalities: (a) a sensor network search which enables users to find a sensor networks appropriate for experiment and data acquisition, (b) a sensor data archive which provides users with various sensor data acquired by sensor nodes, and (c) an experimental testbed which enables remote users to evaluate their proposed methodologies.

In recent years, there has been an increasing interest in sensor networks, in which sensor nodes such as temperature or humidity sensors communicate with each other for environmental monitoring and so on. In sensor networks, it is important to reduce the energy consumption, since sensor nodes have limits in battery. Most researches achieve this by reducing sensor amount of transmitted data. However, there is a problem that the amount of transmitted data become large and their energy consumption becomes high when there are a lot of nodes in the sensing area. To solve the problem, we previously proposed a data gathering method. In this method, the data sink estimates the data value of nodes, broadcasts the estimated values, and then, sensor nodes whose observed values are largely different from the estimated values send the data. However, this method has a problem that it cannot sufficiently reduce the energy consumption. In this paper, we propose a new broadcast-based data gathering method. In this method, the data sink reduces the nodes which send their observed values when the reliability of gathered values by the data sink is high.

In mobile ad hoc networks, when a mobile host receives a data request from another host, the host usually transmits the requested data item by unicast. However, if mobile hosts hold data items that are frequently requested by others, they have to transmit the data items many times and consume a large amount of power. In this paper, we propose a data transmission method for not only maintaining data availability but also reducing traffic for data access. In our proposed method, each mobile host sends a data request attached with the deadline to receive the requested data item by the determined time. Moreover, each mobile host collects multiple requests for data items and transmits the requested data items by multicast, and thus, reduces data traffic. We also show the results of simulation experiments regarding the performance of our proposed method.

Geographical context is very important for images. Millions of images on the Web have been already assigned latitude and longitude information. Due to the rapid proliferation of such images with geographical context, it is still difficult to effectively search and browse them, since we do not have ways to decide their relevance. In this paper, we focus on the geographical relevance of images, which is defined as to what extent the main objects in an image match landmarks at the location where the image was taken. Recently, researchers have proposed to use game based approaches to label large scale data such as Web images. However, previous works have not shown the quality of collected game logs in detail and how the logs can improve existing applications. To answer these questions, we design and implement a Web-based and multi-player game to collect human knowledge while people are enjoying the game. Then we thoroughly analyze the game logs obtained during a three week study with 147 participants and propose methods to determine the image geographical relevance. In addition, we conduct an experiment to compare our methods with a commercial search engine. Experimental results show that our methods dramatically improve image search relevance. Furthermore, we show that we can derive geographically relevant objects and their salient portion in images, which is valuable for a number of applications such as image location recognition.

Wikipedia, a huge scale Web based encyclopedia, attracts great attention as an invaluable corpus for knowledge extraction because it has various impressive characteristics such as a huge number of articles, live updates, a dense link structure, brief anchor texts and URL identification for concepts. We have already proved that we can use Wikipedia to construct a huge scale accurate association thesaurus. The association thesaurus we constructed covers almost 1.3 million concepts and its accuracy is proved in detailed experiments. However, we still need scalable methods to analyze the huge number of Web pages and hyperlinks among articles in the Web based encyclopedia.

In this paper, we investigate adaptive control for broadcast scheduling and base station caching in the hybrid wireless broadcast (HWB) environment. The proposed adaptive method can adapt well to different access conditions and bandwidth capabilities and adequately exploit the three data delivery modes: push-based broadcast, pull- based broadcast, and pull-based point-to-point communication. Simulation studies demonstrated that our proposed method achieves significant performance improvement in average waiting time and success rate.

In mobile ad hoc networks, a mobile host holding data items frequently accessed by other hosts needs to transmit them many times and consumes more power than other hosts. In this paper, we propose replica allocation methods for not only improving data availability but also balancing the power consumption among mobile hosts. In these methods, each mobile host replicates data items taking into account their access frequencies, the numbers of their replicas, and the host's remaining battery power. We present simulation results to evaluate the performance of our proposed methods.

In this paper, based on the Hybrid Wireless Broadcast (HWB) model, we investigate a cooperative data management strategy to provide more efficient data delivery to the mobile clients. This strategy integrates broadcast scheduling with cache management of the base station by making effective use of the HWB data dissemination, namely push- and pull- based broadcast and pull-based point-topoint wireless communication. Simulation study demonstrates that the proposed cooperation strategy can improve the system performance.

In mobile ad hoc networks where data items are updated, each mobile host cannot verify whether its own replica is the same version as the original when it does not connect to the mobile host holding the original (original holder). In this paper, we propose two update log dissemination methods that efficiently verify the validity of tentative accesses to replicas. In the first method, the original holder efficiently disseminates the update logs to other hosts. In the other method, mobile hosts which are not the original holder also manage the update logs and two newly connected mobile hosts re-disseminate the logs. We also present simulation results to evaluate the performance of our methods.

In this paper, we propose a TDMA slot assignment protocol to realize the high channel utilization in an ad hoc sensor network where nodes have different communication ranges. Our protocol prevents inconsistency of the slot assignment information by considering the directions of wireless links with the neighbors when each node assigns a slot to itself. Furthermore, we verify the effectiveness of our protocol by simulation experiments. The results show that our protocol utilizes the channel bandwidth effectively even when nodes have different communication ranges.

In recent years, there has been an increasing interest in broadcast database systems, where the server periodically broadcasts contents of a database to mobile clients such as PDAs. There are three query processing methods in the broadcast database system: (i) the server processes a query and then broadcasts the query result to the client; (ii) the client stores all data that are necessary in processing the query and then processes it locally; and (iii) the server and the client collaborate in processing the query. Since the performance of each method changes according to the system situation, such as query frequency, it is difficult to decide the optimal method among them statically. In this paper, we propose a new query processing method which dynamically changes the query processing method based on query frequency. This method improves not only the response time but also the success rate of query processing compared with the traditional methods.

In this paper, we introduce two our approaches to browse large Web pages designed for desktop PCs using mobile devices with small screens and poor input interfaces. In the first approach, multiple mobile users collaboratively browse large Web pages. We call this approach collaborative browsing. In the second approach, automatic scrolling in a large Web page is performed, where contents in the page are traversed. This enables users to rapidly view the page with the users’ minimum operations.

GeoNote.net is a social network system which allows users to share geographic information among their friends network. The system has various notable features and uses several key technologies such as social network construction methods, security for personal information, geographic information management on mobile devices including cellular phones, retrieval of geographic information according to the friends network, and so on. In this paper, we describe the system under design aspects and implementation aspects.

Data replication is effective for improving data availability in ad hoc networks. In an environment where data updates occur, replicas of a data item may be inconsistent. To solve this problem, quorum based consistency management is a promising approach. To reduce communication overhead, it is better to make the number of mobile hosts in each quorum small. In this paper, we propose a consistency management method that constructs quorums with fewer mobile hosts.

Recently, there has been an increasing interest in a social network. In a social network, nodes and links represent participants and their friendships, respectively. We have designed and implemented a query propagation mechanism and its applications to realize a social network composed by cellular phone users. In these applications, users can retrieve information from their friends or their friends’ friends by propagating the query in the network. To propagate a query in a wide range and improve the query success ratio, most users who receive the query must relay it to all their friends. However, this increases communication packets. In this paper, we propose a query routing method to decrease the number of communication packets by using user profiles.

It is difficult for users of mobile devices such as cellular phones equipped with a small screen and a poor input interface to browse Web pages designed for desktop PCs with large displays. Many studies and commercial products have tried to solve this problem. Web pages include images that have various roles such as site menus, line headers for itemization, and page titles. However, most studies of mobile Web browsing haven't paid much attention to the roles of Web images. In this paper, we define eleven Web image categories according to their roles and use these categories for proper Web image handling. We manually categorized 3,901 Web images collected from forty Web sites and extracted image features of each category according to the classification. By making use of the extracted features, we devised an automatic Web image classification method. Furthermore, we evaluated the automatic classification of real Web pages and achieved up to 83.1% classification accuracy. We also implemented an automatic Web page scrolling system as an application of our automatic image classification method.

Recent advances in computer and wireless communication technologies have increased interest in push-based information systems in which a server repeatedly broadcasts data to clients through a broadband channel. In this paper, assuming an environment where clients in push-based information systems construct ad hoc networks, we propose three caching strategies in which clients cooperatively cache broadcast data items. These strategies shorten the average response time for data access by replacing cached items based on their access frequencies, the network topology, and the time remaining until each item is broadcast next. We also show the results of simulation experiments conducted to evaluate the performance of our proposed strategies.

Recent advances in computer and wireless communication technologies have led to an increasing interest in ad hoc networks which are temporarily constructed by only mobile hosts. In ad hoc networks, since mobile hosts move freely, disconnections occur frequently, and this causes frequent network division. Consequently, data accessibility in ad hoc networks is lower than that in the conventional fixed networks. Assuming an environment where each data item is periodically updated, we propose three replica allocation methods to improve data accessibility by replicating data items on mobile hosts. In these three methods, we take into account the access frequency from mobile hosts to each data item, the status of the network connection, and the time remaining until each item is updated next. We also show the results of simulation experiments regarding the performance evaluation of our proposed methods.

Because of the recent development of network technologies such as ATM (Asynchronous Transfer Mode), broader channel bandwidth is becoming available everywhere in the world wide networks. As one of the new technologies to make good use of such broadband channel, dynamic relocation of databases through networks, which we call database migration, will soon become a powerful and basic database operation of practical use. We discuss our proposal of a distributed database system, DB-MAN (distributed database system based on DataBase Migration in ATM Networks), which takes advantage of database migration in virtual LANs (local area networks) of ATM networks. DB-MAN has two notable mechanisms: a mechanism for selecting the transaction processing method and a mechanism for concurrency control with database migration. The former, is a mechanism which chooses the more efficient method between two transaction processing methods: the conventional method based on the two phase commit protocol and our method employing database migration. The latter is a mechanism to prevent the transaction processing throughput from deteriorating in environments where data contention is a significant factor. Then we show simulation results regarding performance comparison between our proposed system and the conventional distributed database system based on the two phase commit protocol. The obtained results demonstrate that effective use of database migration gives higher performance than that of the conventional system.

Due to recent developments in network technologies, broader channel bandwidth is becoming prevalent in worldwide networks. As one of the new technologies making good use of such broadband channels, dynamic relocation of databases through networks, database migration, will soon be used in practice as a powerful and basic database operation. We propose two transaction processing methods to take advantage of database migration in broadband networks. These methods choose the most efficient transaction processing method between the conventional method, based on the two-phase commit protocol, and our method, using database migration. We also propose a concurrency control mechanism and a recovery mechanism for our proposed methods. Simulation results are presented comparing the performance of our proposed methods and the conventional transaction processing method based on the two-phase commit protocol. The results demonstrate that the effective use of database migration produces better performance than the conventional method.