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.

How can we mine frequent path regularities from a graph with edge labels and vertex attributes? The task of association rule mining successfully discovers regular patterns in item sets and substructures. Still, to our best knowledge, this concept has not yet been extended to path patterns in large property graphs. In this paper, we introduce the problem of path association rule mining (PARM). Applied to any reachability path between two vertices within a large graph, PARM discovers regular ways in which path patterns, identified by vertex attributes and edge labels, co-occur with each other. We develop an efficient and scalable algorithm PIONEER that exploits an anti-monotonicity property to effectively prune the search space. Further, we devise approximation techniques and employ parallelization to achieve scalable path association rule mining. Our experimental study using real-world graph data verifies the significance of path association rules and the efficiency of our solutions.

Nowadays, so as to improve services and urban area livability, multiple smart city initiatives are being carried out throughout the world. SmartSantander is a smart city project in Santander, Spain, which has relied on wireless sensor network technologies to deploy heterogeneous sensors within the city to measure multiple parameters, including outdoor parking information. In this paper, we study the prediction of parking lot availability using historical data from more than 300 outdoor parking sensors with SmartSantander. We design a graph-to-sequence model to capture the periodical fluctuation and geographical proximity of parking lots. For developing and evaluating our model, we use a 3-year dataset of parking lot availability in the city of Santander. Our model achieves a high accuracy compared with existing sequence-to-sequence models, which is accurate enough to provide a parking information service in the city. We apply our model to a smartphone application to be widely used by citizens and tourists.

Generating large synthetic attributed graphs with node labels is an important task to support various experimental studies for graph analytic methods. Existing graph generators fail to simultaneously simulate core/border and homophily/heterophily phenomena which real-world graphs exhibit, i.e., the relationships between labels, attributes, and topology. Motivated by this limitation, we propose GenCAT, an attributed graph generator for controlling those relationships, which has the following advantages. (i) GenCAT generates graphs with user-specified node degrees and flexibly controls the relationship between nodes and labels by incorporating the connection proportion for each node to classes. (ii) Generated attribute values follow user-specified distributions, and users can flexibly control the correlation between the attributes and labels. (iii) Graph generation scales linearly to the number of edges. GenCAT is the first generator to support all three of these practical features, i.e., it can capture both core/border and homophily/heterophily phenomena while ensuring its scalability. Through extensive experiments, we demonstrate that GenCAT can efficiently generate high-quality complex attributed graphs with user-controlled relationships between labels, attributes, and topology.

The Steiner tree enumeration problem is a well-known problem that asks for enumerating Steiner trees. Although numerous theoretical works proposed algorithms for the problem and analyzed their complexity, there are no practical algorithms and empirical studies. In this paper, we first study the Steiner tree enumeration problem practically. First, we define a practical problem cost-constrained minimal Steiner tree enumeration problem, which enumerates minimal Steiner trees with costs not larger than a given threshold. Second, to address the problem, we propose a binary decision diagram (BDD)-based algorithm. The BDD-based algorithm constructs a BDD that compactly represents the set of minimal Steiner trees and then traverses the BDD for enumeration. We develop a novel frontier-based algorithm to construct such BDDs efficiently. Furthermore, we extend our algorithm to be scalable for large-scale graphs by preprocessing the given graph and controlling the number of generated Steiner trees to reduce memory and computation costs. We validate that our algorithm can efficiently enumerate minimal Steiner trees in real-world graphs.

Conjunctive path queries (CPQ) are one of the most frequently used queries for complex graph analysis. However, current graph indexes are not tailored to fully support the power of query languages to express CPQs. Consequently, current methods do not take advantage of significant pruning opportunities during$CPQ$evaluation, resulting in poor query processing performance. We propose the CPQ-aware path index CPQx, the first path index tailored to the expressivity of CPQ. CPQx is built on the partition of the set of source-target vertex pairs of paths in a graph based on the structural notion of path-bisimulation. Path-bisimulation is an equivalence relation on paths such that each partition block induced by the relation consists of paths in the graph indistinguishable with respect to CPQs. This language-aware partitioning of the graph can significantly reduce the cost of query evaluation. We present methods to support the full index life cycle: index construction, maintenance, and query processing with our index. We also develop interest-aware CPQx to reduce index size and index construction overhead while accelerating query evaluation for queries of interest. We demonstrate through extensive experiments on 14 real graphs that our methods accelerate query processing by up to multiple orders of magnitude over the state-of-the-art methods, with smaller index sizes. Our complete C++ codebase is available as open source for further research.

Urban air pollution is a major environmental problem affecting human health and quality of life. Monitoring stations have been established to obtain air quality information continuously, but they do not cover all areas. Thus, there are numerous methods for spatially fine-grained air quality inference. Since existing methods aim to infer air quality of locations only in monitored cities, they do not assume inferring air quality in unmonitored cities. In this paper, we first study the air quality inference in unmonitored cities. To accurately infer air quality in unmonitored cities, we propose a neural network-based approach AIREX. The novelty of AIREX is employing a mixture-of-experts approach, a machine learning technique based on the divide-and-conquer principle, to learn correlations of air quality between multiple cities. To further boost the performance, it employs attention mechanisms to compute the impacts of air quality inference from the monitored cities to the locations in the unmonitored city. Through experiments on a real-world air quality dataset, we show that AIREX achieves higher accuracy than state-of-the-art methods.

Federated learning is a distributed machine learning method in which a single server and multiple clients collaboratively build machine learning models without sharing datasets on clients. Numerous methods have been proposed to cope with the data heterogeneity issue in federated learning. Existing solutions require a model architecture tuned by the central server, yet a major technical challenge is that it is difficult to tune the model architecture due to the absence of local data on the central server. In this paper, we propose Federated learning via Model exchange (FedMe), which personalizes models with automatic model architecture tuning during the learning process. The novelty of FedMe lies in its learning process: clients exchange their models for model architecture tuning and model training. First, to optimize the model architectures for local data, clients tune their own personalized models by comparing to exchanged models and picking the one that yields the best performance. Second, clients train both personalized models and exchanged models by using deep mutual learning, in spite of different model architectures across the clients. We perform experiments on three real datasets and show that FedMe outperforms state-of-the-art federated learning methods while tuning model architectures automatically.

Abstract This article addresses a new pattern mining problem in time series sensor data, which we call correlated attribute pattern mining. The correlated attribute patterns (CAPs for short) are the sets of attributes (e.g., temperature and traffic volume) on sensors that are spatially close to each other and temporally correlated in their measurements. Although the CAPs are useful to accurately analyze and understand spatio-temporal correlation between attributes, the existing mining methods are inefficient to discover CAPs because they extract unnecessary patterns. Therefore, we propose a mining method Miscela to efficiently discover CAPs. Miscela can discover not only simultaneous correlated patterns but also time delayed correlated patterns. Furthermore, we extend Miscela to automatically search for correlated patterns with any time delays. Through our experiments using three real sensor datasets, we show that the response time of Miscela is up to 20.84 times faster compared with the state-of-the-art method. We show that Miscela discovers meaningful patterns for urban managements and environmental studies.

We propose a novel edge generation procedure, Community-aware Edge Generation (CEG), which controls the internal structure of communities: hub dominance and clustering coefficient. CEG is designed to be adaptable to existing graph generators. We demonstrate the effectiveness of CEG from three aspects. First, we validate that CEG generates graphs with similar internal structures to given real-world graphs. Second, we show how the parameters of CEG control the internal structure of communities. Finally, we show that CEG can generate various types of internal structures of communities by visualizing generated graphs.

Estimating land prices is useful for assessing values of sites. Several works study estimating land prices from land features that are extracted from geodetic data. However, the estimation accuracy is not high enough yet because it is difficult to thoroughly collect geodetic data that affects land prices. In this paper, we study the effectiveness of the satellite images to estimate land prices for the first time. To verify effectiveness of satellite images, we estimate land prices by using three deep neural network models: multilayer perceptrons (MLP) model only with geodetic data, convolution neural network (CNN) model only with satellite images, and concatenation model that concatenates the MLP with the CNN models. We demonstrate through experiments using real land prices, geodetic data, and satellite images in Japan that the simultaneous use of satellite images and geodetic data improves the estimation accuracy of land prices.

The urban condition is monitored by a wide variety of sensors with several attributes such as temperature and traffic volume. It is expected to discover the correlated attributes to accurately analyze and understand the urban condition. Several mining techniques for spatio-temporal data have been proposed for discovering the sets of sensors that are spatially close to each other and temporally correlated in their measurements. However, they cannot discover correlated attributes efficiently because their targets are correlated sensors with a single attribute. In this paper, we introduce a problem of discovering correlations among multiple attributes, which we call correlated attribute pattern (CAP) mining. Although the existing spatio-temporal data mining methods can be extended to discover CAPs, they are inefficient because they extract unnecessary correlated sensors that do not have CAPs. Therefore, we propose a CAP mining method MISCELA to efficiently discover CAPs. In MISCELA, we develop a new tree structure called CAP search tree, by which we can effectively prune the unnecessary patterns for the CAP mining. Our experiments using real sensor datasets show that the response time of MISCELA is up to 79% faster compared to the state-of-the-art.

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.

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.

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.

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.