Patch-wise Transformer based time series forecasting achieves superior accuracy. However, this superiority relies heavily on intricate model design with massive parameters, rendering both training and inference expensive, thus preventing their deployments on edge devices with limited resources and low latency requirements. In addition, existing methods often work in an autoregressive manner, which take into account only historical values, but ignore valuable, easy-to-obtain context information, such as weather forecasts, date and time of day. To contend with the two limitations, we propose LiPFormer, a novel Lightweight Patch-wise Transformer with weak data enriching. First, to simplify the Transformer backbone, LiPFormer employs a novel lightweight cross-patch attention and a linear transformationbased attention to eliminate Layer Normalization and Feed Forward Network, two heavy components in existing Transformers. Second, we propose a lightweight, weak data enriching module to provide additional, valuable weak supervision to the training. It enhances forecasting accuracy without significantly increasing model complexity as it does not involve expensive, human-labeling but using easily accessible context information. This facilitates the weak data enriching to plug-and-play on existing models. Extensive experiments on nine benchmark time series datasets demonstrate that LiPFormer outperforms state-of-the-art methods in accuracy, while significantly reducing parameter scale, training duration, and GPU memory usage. Deployment on an edge device reveals that LiPFormer takes only 1/3 inference time compared to classic Transformers. In addition, we demonstrate that the weak data enriching can integrate seamlessly into various Transformer based models to enhance their accuracy, suggesting its generality.

Collective Location Selection (CLS) aims to identify$k$optimal sites for facility establishment to collectively maximize user attraction. Traditional CLS approaches often overlook user mobility and inter-facility competition, critical factors in real-world scenarios. This paper introduces MC2LS, the first effort on CLS that addresses these gaps by considering user mobility and peer competition. Solving MC2LS is nontrivial due to its NP-hardness. To overcome the challenge of pruning multi-point users with highly overlapping minimum boundary rectangles (MBRs), we develop a position count threshold and two square-based pruning rules. We propose IQuad-tree, a user-MBR-free index, to benefit the hierarchical and batch-wise properties of the pruning rules. We present an$(1-\frac{1}{e})$-approximate greedy solution to MC2LS, and empirical studies demonstrate the superiority of our proposed solution over the state-of-the-art techniques.

Collective Location Selection (CLS) has received significant research attention in the spatial database community due to its wide range of applications. The CLS problem selects a group ofkpreferred locations among candidate sites to establish facilities, aimed at collectively attracting the maximum number of users. Existing studies commonly assume every user is located in a fixed position, without considering the competition between peer facilities. Unfortunately, in real markets, users are mobile and choose to patronize from a host of competitors, making traditional techniques unavailable. To this end, this paper presents the first effort on a CLS problem in competition scenarios, calledmc$^{2}$2ls, taking into account the mobility factor. Solvingmc$^{2}$2lsis a non-trivial task due to its NP-hardness. To overcome the challenge of pruning multi-point users with highly overlapped minimum boundary rectangles (MBRs), we exploit a position count threshold and design two square-based pruning rules. We introduce IQuad-tree, a user-MBR-free index, to benefit the hierarchical and batch-wise properties of the pruning rules. We propose an$(1-\frac{1}{e})$-approximate greedy solution tomc$^{2}$2lsand incorporate a candidate-pruning strategy to further accelerate the computation for handling skewed datasets. Extensive experiments are conducted on real datasets, demonstrating the superiority of our proposed pruning rules and solution compared to the state-of-the-art techniques.

Facility Relocation (FR), which is an effort to reallocate the placement of facilities to adapt to the changes of urban planning, has remarkable impact on many areas. Existing solutions fail to guarantee the result quality on relocating k > 1 facilities. As k -FR problem is NP-complete and is not submodular or non-decreasing, traditional greedy algorithm cannot be directly applied. We propose to transform k -FR into another facility placement problem, which is submodular and non-decreasing. We prove that the optimal solutions of both problems are equivalent. Accordingly, we present the first approximate solution toward the k -FR, FR2FP. Our extensive comparison over both FR2FP and the state-of-the-art solution shows that FR2FP, although it provides approximation guarantee, cannot necessarily given superior results. The comparison motivates us to present an advanced approximate solution, FR2FP-ex. Moreover, based on Lagrangian relaxation, we develop an algorithm that can adjust the approximation ratio. Extensive experiments verified that, FR2FP-ex demonstrates the best result quality, and it is very close to the optimal solution. In addition, we also unveil the scenarios when the state-of-the-art would fail. We further generalize the k -FR problem, considering the budget for relocation and the cost of each facility. We also present corresponding approximate solutions toward the new problem and prove the approximation ratio.

Facility Relocation (FR), which is an effort to reallocate the placement of facilities to adapt to the changes of urban planning and population distribution, has remarkable impact on many application areas. Existing solutions to the FR problem either focus on relocating one facility (ie 1-FR) or fail to guarantee the result quality on relocating k>1 facilities (ie k-FR). As k-FR problem is NP-hard and is not submodular or non-decreasing, traditional hill-climb approximate algorithm cannot be directly applied. In light of that, we propose to transform k-FR into another facility placement problem, which is submodular and non-decreasing. We theoretically prove that the optimal solution of both problems are equivalent. Accordingly, we are able to present the first approximate solution towards the k-FR, namely FR2FP. Our extensive comparison over both FR2FP and the state-of-the-art heuristic solution shows that FR2FP, although provides approximation guarantee, cannot necessarily given superior results to the heuristic solution. The comparison motivates and, more importantly, directs us to present an advanced approximate solution, namely FR2FP-ex. Extensive experimental study over both real-world and synthetic datasets have verified that, FR2FP-ex demonstrates the best result quality. In addition, we also exactly unveil the scenarios when the state-of-the-art heuristic would fail to provide satisfied results in practice.

Abstract The location selection (LS) problem identifies an optimal site to place a new facility such that its influence on given objects can be maximized. With the proliferation of GPS-enabled mobile devices, LS studies have made progress for moving objects. However, the state-of-the-art LS techniques over moving objects assume the new facility has no competitor, which is too restrictive and unrealistic for real-world business. In this paper we study Competitive Location Selection over Moving objects (CLS-M), which takes into account competition against existing facilities in mobile scenarios. We present a competition-based influence score model to evaluate the influence of a candidate. To solve the problem, we propose an influence pruning algorithm to prune objects who are either influenced by inferior candidates or affected by no candidate. Experimental study over two real-world datasets demonstrates that the proposed algorithm outperforms state-of-the-art LS techniques in terms of efficiency.

The facility relocation (FR) problem, which aims to optimize the placement of facilities to accommodate the changes of users’ locations, has a broad spectrum of applications. Despite the significant progress made by existing solutions to the FR problem, they all assume each user is stationary and represented as a single point. Unfortunately, in reality, objects (e.g., people, animals) are mobile. For example, a car-sharing user picks up a vehicle from a station close to where he or she is currently located. Consequently, these efforts may fail to identify a superior solution to the FR problem. In this article, for the first time, we take into account the movement history of users and introduce a novel FR problem, called motion-fr , to address the preceding limitation. Specifically, we present a framework called frost to address it. frost comprises two exact algorithms: index based and index free . The former is designed to address the scenario when facilities and objects are known a priori , whereas the latter solves the motion-fr problem by jettisoning this assumption. Further, we extend the index-based algorithm to solve the general k - motion-fr problem, which aims to relocate k inferior facilities. We devise an approximate solution due to NP-hardness of the problem. Experimental study over both real-world and synthetic datasets demonstrates the superiority of our framework in comparison to state-of-the-art FR techniques in efficiency and effectiveness.

In this paper we propose and study the problem of k-Collective influential facility placement over moving object. Specifically, given a set of candidate locations, a group of moving objects, each of which is associated with a collection of reference points, as well as a budget k, we aim to mine a group of k locations, the combination of whom can influence the most number of moving objects. We show that this problem is NP-hard and present a basic hill-climb algorithm, namely GreedyP. We prove this method with (1 - 1/e ) approximation ratio. One core challenge is to identify and reduce the overlap of the influence from different selected locations to maximize the marginal benefits. Therefore, the GreedyP approach may be very costly when the number of moving objects is large. In order to address the problem, we also propose another GreedyPS algorithm based on FM-sketch technique, which maps the moving objects to bitmaps such that the marginal benefit can be easily observed through bit-wise operations. Through this way, we are able to save more than a half running time while preserving the result quality. Experiments on real datasets verify the efficiency and effectiveness for both algorithms we propose in this paper.

The location selection (LS) problem aims to mine the optimal location to place a new facility from a set of candidates such that the benefit or influence on a given set of objects is maximized. State-of-the-art LS techniques assume each object is static and can only be influenced by a single facility. However, in reality, objects (e.g., people, vehicles) are mobile and are influenced by multiple facilities. Consequently, classical LS solutions fail to select locations accurately. In this work, we introduce a generalized LS problem called PRIME-LS which takes mobility and probability factors into consideration to address the aforementioned limitations. To solve the problem, we propose an algorithm called PINOCCHIO, which leverages two pruning rules based on a novel distance measure, and further extend it by incorporating two optimization strategies. Experimental study over two real-world datasets demonstrates superiority of our framework in comparison to state-of-the-art LS techniques.

The location selection (ls) problem, which aims to mine the optimal location from a set of candidates to place a new facility such that a score (i.e., benefit or influence on some given objects) can be maximized, has drawn significant research attention in recent years. State-of-the-art ls techniques assume each object is static and can only be influenced by a single facility. However, in reality, objects (e.g., people, vehicles) are mobile and are influenced by multiple facilities, which prevents classical ls solutions from selecting accurate results. In this paper, we introduce a generalizedls problem called Prime-ls which takes mobility and probability factors into consideration to address the aforementioned limitations. Specifically, given a set of candidate locations, Prime-ls aims to mine the optimal location which can influence the most number of moving objects. Also, to address the problem we propose an efficient algorithm called Pinocchio that leverages two pruning rules based on a novel distance measure. These rules enable us to prune many inferior candidate locations prior to influence computation, paving the way to efficient and accurate solution. Furthermore, we extend Pinocchio (Pinocchio-vo) by incorporating two optimization strategies during candidate validation phase, which further reduce unnecessary computations. Experimental study over two real-world datasets demonstrates superiority of our framework in comparison to state-of-the-art ls techniques.