Weighted intervals are ubiquitous, because many objects are associated with temporal and numeric dimensions. As interval datasets are usually large, efficient management and processing of large weighted interval data are required. This article addresses the problem of top-k range search on weighted interval data, which retrieves k intervals with the largest weight among a set of intervals overlapping a given query interval. It finds important analytical applications for vehicles, events, and cryptocurrencies. Existing algorithms for range search on interval data are inefficient for this problem, because they need to search for all intervals that overlap a given query interval. To overcome this inefficiency issue, we first provide a baseline algorithm and then propose three data structures, along with their associated algorithms. Our first proposed algorithm is practically fast but requires $$\varvec{O(n\log k)}$$ time, where n is the number of intervals, whereas the others require less than $$\varvec{O(n\log k)}$$ time. Furthermore, we address a duration-constrained variant of the top-k range search problem. To solve this variant efficiently, we extend our algorithms and present how to maintain a time complexity of less than $$\varvec{O(n\log k)}$$ . We conduct extensive experiments on real-world datasets, and the results show that our algorithms outperform baseline techniques in most cases.

Uemura R., Amagata D.. IVF++: A Flexible and Efficient Algorithm for Approximate Nearest Neighbor Search under Attribute Constraint. Proceedings of the IEEE International Conference on Big Data, pp. 7444–7451 (2025); https://doi.org/10.1109/BigData66926.2025.11402093.

Spatial range joins have many applications, including geographic information systems, location-based social networking services, neuroscience, and visualization. However, joins incur not only expensive computational costs but also too large result sets. A practical and reasonable approach to alleviating these issues is to return random samples of the join results. Although this is promising and sufficient for many applications involving spatial range joins, efficiently computing random samples is not trivial. This is because we must obtain random join samples without running spatial range joins. We address this challenging problem for the first time and aim at designing a time- and space-efficient algorithm. First, we design two baseline algorithms that employ existing techniques for random sampling and show that they are not efficient. Then, we propose a new data structure that can deal with our problem in$\tilde{O}(n+m+t)$expected time and$O(n+m)$space, where$n$and$m$are the sizes of two point sets and$t$is the required number of samples. We conduct extensive experiments using four real spatial datasets, and the results demonstrate that our algorithm is significantly faster than the baselines in most tests.

Weighted intervals are ubiquitous because many objects are associated with temporal and numeric dimensions.As interval datasets are usually large, efficient management and processing of large weighted interval data are required.This paper addresses the problem of top-𝑘 range search on weighted interval data, which retrieves 𝑘 intervals with the largest weight among a set of intervals overlapping a given query interval.It finds important analytical applications for vehicles, events, and cryptocurrencies.Existing algorithms for range search on interval data are inefficient for this problem, because they need to search for all intervals that overlap a given query interval.To overcome this inefficiency issue, we first provide a baseline algorithm and then propose two data structures and their associated algorithms.Our first proposed algorithm is practically fast but requires 𝑂 (𝑛 log 𝑘) time, where 𝑛 is the number of intervals, whereas the other requires less than 𝑂 (𝑛 log 𝑘) time.We conduct extensive experiments on real-world datasets, and the results show that our algorithms outperform baseline techniques in most cases.

GPS data analysis is one of the main operators in geographical information systems.However, because of security and privacy issues, we often face situations where GPS data cannot be obtained frequently.Such situations and the measurement errors of GPS coordinates make identifying user behaviors challenging.In this work, we assume this setting and tackle the classification problem of target and non-target categories for the first time.Target categories are store categories in the scope of a service provider, whereas nontarget ones are those that are not in.Given a GPS point, this problem estimates which category this location belongs to, so it is a binary classification problem.This problem has two main difficulties.First, we cannot obtain labeled data of the non-target categories.Second, many GPS data have error ranges and no labels, i.e., they do not clarify where the users stay.To solve the problem while addressing these difficulties, we propose a new classification method based on machine learning.We exploit GPS and check-in data to obtain user feature vectors at a given time.Our loss function considers nonstay information on each store category to identify the non-target space in the feature space.From these techniques, we compute the probability of staying in one of the (non-)target categories.We conduct experiments on real-world datasets, and the results show the effectiveness of our method.

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.

Many applications require efficient management of large sets of intervals because many objects are associated with intervals (e.g., time and price intervals). In such interval management systems, range search is a primitive operator for retrieving and analysis tasks. As dataset sizes are growing nowadays, range search results are also becoming larger, which may overwhelm users and incur long computation time. Because applications are usually satisfied with a subset of the result set, it is desirable to efficiently obtain only small samples from the result set. We therefore address the problem of independent range sampling on interval data, which outputs$s$random samples that overlap a given query interval and are independent of the samples of all previous queries. To efficiently solve this problem theoretically and practically, we propose a variant of an interval tree, namely the augmented interval tree (or AIT), and we show that there exists an exact algorithm that needs$O(n\log n)$space and$O(\log^{2}n+s)$time, where$n$is the dataset size. The simple structure of an AIT provides flexible extensions: (i) its time and space complexities respectively become$O(\log^{2}n+s)$expected and$O(n)$by bucketing intervals and (ii) it can deal with weighted intervals and outputs$s$weighted random samples in$O(\log^{2}n+s\log n)$time. We conduct extensive experiments on real datasets, and the results demonstrate that our algorithms significantly outperform competitors.

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.

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.

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.

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.

Clustering is a primitive and important operator that analyzes a given dataset to discover its hidden patterns and features. Because datasets are usually updated dynamically (i.e., it accepts continuous insertions and arbitrary deletions), analyzing such dynamic data is also an important topic, and dynamic clustering effectively supports it, but is a challenging problem. In this paper, we consider the problem of density-peaks clustering (DPC) on dynamic data. DPC is one of the density-based clustering algorithms and attracts attention for many applications, due to its effectiveness. We investigate the hardness of this problem theoretically to measure the efficiencies of dynamic DPC algorithms. We prove that any exact solutions are costly, and propose an approximation algorithm to enable faster updates. We conduct experiments on real datasets, and the results confirm that our algorithm is much faster and more accurate than state-of-the-art.

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.

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.

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.

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.

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.

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.