Diverse types of edge data, such as 2D geo-locations and 3D point clouds, are collected by sensors like lidar and GPS receivers on edge devices. On-device searches, such as k-nearest neighbor (kNN) search and radius search, are commonly used to enable fast analytics and learning technologies, such as k-means dataset simplification using kNN. To maintain high search efficiency, a representative approach is to utilize a balanced multi-way KD-tree (BMKD-tree). However, the index has shown limited gains, mainly due to substantial construction overhead, inflexibility to real-time insertion, and inconsistent query performance. In this paper, we propose UnIS to address the above limitations. We first accelerate the construction process of the BMKD-tree by utilizing the dataset distribution to predict the splitting hyperplanes. To make the continuously generated data searchable, we propose a selective sub-tree rebuilding scheme to accelerate rebalancing during insertion by reducing the number of data points involved. We then propose an auto-selection model to improve query performance by automatically selecting the optimal search strategy among multiple strategies for an arbitrary query task. Experimental results show that UnIS achieves average speedups of 17.96x in index construction, 1.60x in insertion, 7.15x in kNN search, and 1.09x in radius search compared to the BMKD-tree. We further verify its effectiveness in accelerating dataset simplification on edge devices, achieving a speedup of 217x over Lloyd's algorithm.

Low-rank adaptation (LoRA) has emerged as an efficient fine-tuning technique for large language models, enabling parameter-efficient updates while maintaining task performance. However, LoRA suffers from two key issues: 1) inefficient feature learning when the width n (embedding dimension) is large, and 2) ineffective updates to the adapter matrix A due to the initialization of B as zero. We propose LoRA-E2, which utilizes a Gaussian initialization with variance Θ(n-3/4) for A, and employs the Gauss-Seidel iteration to train B and A. We theoretically show that LoRA-E2 enables more stable and efficient feature learning with effective parameter updates over standard LoRA. Empirically, LoRA-E2 achieves consistent gains in both natural language understanding and generation tasks. On the GLUE benchmark with T5-base, it improves performance by 1-10% over LoRA. When fine-tuning LLaMA 2-7B on MetaMathQA with GSM8K as validation, LoRA-E2 surpasses LoRA by 1-2% and converges up to ∼1/43× faster. Code is available at https://github.com/whu-totemdb/LoRA-E2.

The$k$-means algorithm can simplify large-scale spatial vectors, such as 2D geo-Locations and 3D point clouds, to support fast analytics and learning. However, when processing large-scale datasets, existing$k$-means algorithms have been developed to achieve high performance with significant compu-tational resources, such as memory and CPU usage time. These algorithms, though effective, are not well-suited for resource-constrained devices. In this paper, we propose a fast, memory-efficient, and cost-predictable$k$-means called Dask-means. We first accelerate$k$-means by designing a memory-efficient accelerator, which utilizes an optimized nearest neighbor search over a memory-tunable index to assign spatial vectors to clusters in batches. We then design a lightweight cost estimator to predict the memory cost and runtime of the k-means task, allowing it to request appropriate memory from devices or adjust the accelerator's required space to meet memory constraints, and ensure sufficient CPU time for running k-means. Experiments show that when simplifying datasets with scale such as$10^{6}$, Dask-means uses less than 30MB of memory, and achieves over 168 times speedup compared to the widely-used Lloyd's algorithm. We also validate Dask-means on mobile devices, where it demonstrates significant speedup and low memory cost compared to other state-of-the-art (SOTA)$k$-means algorithms. Our cost estimator achieves a memory cost estimation error with a difference of less than 3% from the actual ones and an MSE for predicted runtime at least 52.1 % lower than SOTA methods.

Vector set search, an underexplored similarity search paradigm, aims to find vector sets similar to a query set. This search paradigm leverages the inherent structural alignment between sets and real-world entities to model more fine-grained and consistent relationships for diverse applications. This task, however, faces more severe efficiency challenges than traditional single-vector search due to the combinatorial explosion of pairings in set-to-set comparisons. In this work, we aim to address the efficiency challenges posed by the combinatorial explosion in vector set search, as well as the curse of dimensionality inherited from single-vector search. To tackle these challenges, we present an efficient algorithm for vector set search, BioVSS (Bio-inspired Vector Set Search). BioVSS simulates the fly olfactory circuit to quantize vectors into sparse binary codes and then designs an index based on the set membership property of the Bloom filter. The quantization and indexing strategy enables BioVSS to efficiently perform vector set search by pruning the search space. Experimental results demonstrate over 50 times speedup compared to linear scanning on million-scale datasets while maintaining a high recall rate of up to 98.9%, making it an efficient solution for vector set search.

The search for joinable data is pivotal for numerous applications, such as data integration, data augmentation, and data analysis. Although there have been many successful joinable search studies for table discovery, the study of finding joinable spatial datasets for a given query from multiple spatial data sources has not been well considered. This paper studies two cases of joinable search problems from multiple spatial data sources. In addition to the overlap joinable search problem (OJSP), we also propose a novel coverage joinable search problem (CJSP) that has not been considered before, motivated by many real-world applications in the field of spatial search. To support two cases of joinable search over multiple spatial data sources seamlessly, we propose a multi-source spatial dataset search framework. Firstly, we design a DIstributed Tree-based Spatial index structure called DITS, which is used not only to design acceleration strategies to speed up joinable searches, but also to support efficient communication between multiple data sources. Additionally, we prove that the CJSP is NP-hard and design a greedy approximate algorithm to solve the problem. We evaluate the efficiency of our search framework on five real-world data sources, and the experimental results show that our framework can significantly reduce running time and communication costs compared with baselines.

In federated learning (FL), the assumption that datasets from different devices are independent and identically distributed (i.i.d.) often does not hold due to user differences, and the presence of various data modalities across clients makes using a single model impractical. Personalizing certain parts of the model can effectively address these issues by allowing those parts to differ across clients, while the remaining parts serve as a shared model. However, we found that partial model personalization may exacerbate client drift (each client's local model diverges from the shared model), thereby reducing the effectiveness and efficiency of FL algorithms. We propose an FL framework based on the alternating direction method of multipliers (ADMM), referred to as FedAPM, to mitigate client drift. We construct the augmented Lagrangian function by incorporating first-order and second-order proximal terms into the objective, with the second-order term providing fixed correction and the first-order term offering compensatory correction between the local and shared models. Our analysis demonstrates that FedAPM, by using explicit estimates of the Lagrange multiplier, is more stable and efficient in terms of convergence compared to other FL frameworks. We establish the global convergence of FedAPM training from arbitrary initial points to a stationary point, achieving three types of rates: constant, linear, and sublinear, under mild assumptions. We conduct experiments using four heterogeneous and multimodal datasets with different metrics to validate the performance of FedAPM. Specifically, FedAPM achieves faster and more accurate convergence, outperforming the SOTA methods with average improvements of 12.3% in test accuracy, 16.4% in F1 score, and 18.0% in AUC while requiring fewer communication rounds.

Balanced k -means ensures representative centroids by forming equal-sized clusters, but struggles with slow clustering of massive distributed attributes and data-sharing restrictions. A common approach is adapting it to a vertical federated learning (VFL) framework, preventing raw data exposure by only intermediate result exchange and accelerating clustering via parallelism, yet it remains unexplored. In this paper, we propose a time-efficient, federated, and balanced k -means algorithm, called Teb-means, to bridge the gap. We first formulate the balanced k -means problem as a trace maximization problem (TMP) and propose an efficient coordinate-wise optimization (CO) scheme to solve it. We then integrate TMP and CO into the VFL framework by demonstrating that TMP can be decomposed into multiple subproblems based on each party's data, which can be solved using CO while exchanging only intermediate results. Notably, we build a trade-off between utility and communication efficiency by designing a greedy block-based strategy for CO (GBCO). Our theoretical analysis shows that Teb-means achieves linear time complexity on each client, and our communication round is constant in the mild condition. Experiments show that Teb-means is on average 12.18× faster than other balanced clustering algorithms that can be federated, while achieving better balance without disrupting the cluster structure.

The development of cloud computing has met the growing demand for dataset search in the era of massive data. In the field of spatial dataset search, the high prevalence of sensitive information in spatial datasets underscores the necessity of privacy-preserving search processing in the cloud. However, existing spatial dataset search schemes are designed on plaintext datasets and do not consider privacy protection in search processing. In this paper, we first propose a privacy-preserving spatial dataset search scheme. The density distribution-based similarity model is proposed to measure the similarity between spatial datasets, and then the order-preserving encrypted similarity is designed to achieve secure similarity calculation. With the above idea, the baseline search scheme (PriDAS) is proposed. To improve the search efficiency, a two-layer index is designed to filter candidate datasets and accelerate the similarity calculation between datasets. By using the index, the optimized search scheme (PriDAS+) is proposed. To analyze the security of the proposed schemes, the game simulation-based proof is presented. Experimental results on three real-world spatial data repositories with 100,000 spatial datasets show that PriDAS+ only needs less than 0.4 seconds to accomplish the search processing.

In this paper, we investigate the hybrid regret min-imization (HRM) query, a new method to extract representative tuples from databases. The HRM query combines the two types of regret minimization queries in the literature, namely maximum regret minimization (MRM) and average regret minimization (ARM) queries, aiming to select a size-k subset of tuples from a database to simultaneously minimize the maximum and average regret ratios. We show the NP-hardness of the HRM problem and propose an asymptotic algorithmic (AA) framework with several optimization techniques and a multiplicative weights update (MWU) algorithm to process HRM queries efficiently with theoretical guarantees. Finally, we demonstrate that our proposed algorithms achieve better performance for HRM queries than existing methods specific to MRM and ARM queries through extensive experiments on real-world and synthetic datasets.

Regret minimization queries are important methods to extract representative tuples from databases. They have been extensively investigated in the last decade due to wide applications in multi-criteria decision making. For a given database$D$and a class$\mathcal {F}$of utility functions (e.g., all nonnegative linear functions), two typical regret minimization queries considered in existing studies are maximum regret minimization (MRM) and average regret minimization (ARM) queries, whereby a subset of$k$tuples is selected from$D$to minimize the maximum or average of regret ratios among all utility functions in$\mathcal {F}$, respectively. However, due to the different properties of maximum and average regret ratios, the result of one query cannot fulfill the requirement of the other. To the best of our knowledge, there has not yet been any attempt to combine both queries. In this paper, we first introduce the hybrid regret minimization (HRM) query, which simultaneously minimizes the maximum and average regret ratios. We show that finding the optimal result for an HRM query is NP-hard, but it is possible to exploit submodularity for approximate HRM query processing. We propose an efficient asymptotic approximation algorithm based on submodular maximization to process HRM queries and several optimization techniques, such as memoization, lazy evaluation, and stochastic subsampling, to improve query efficiency. Furthermore, we consider extending a multiplicative weights update (MWU) algorithm for multi-objective submodular maximization to provide higher-quality results for HRM queries. Finally, we demonstrate that our proposed algorithms achieve better performance for HRM queries than existing methods specific to MRM and ARM queries through extensive experiments on real-world and synthetic datasets. Meanwhile, our proposed algorithms are efficient and scalable to large datasets.

This paper studies the problem of fair clustering on heterogeneous information networks (HINs) by considering constraints on structural and sensitive attributes. We propose a Prerequisite-driven Fair Clustering (PDFC ) algorithm to solve this problem. Specifically, we define the structural constraint on the connection among nodes in HINs by combining meta-paths and prerequisite meta-paths and introduce Fairlets as the balance constraint. Under two constraints, we learn node embeddings based on graph models and perform theCholesky decomposition to obtain their orthogonal embeddings. We fuse node embeddings under constraints, define the loss function of PDFC, and perform k-means to achieve clustering. In addition, we design an update strategy of the adjacency matrix to achieve dynamic PDFC over time. Compared with several fair clustering algorithms on three real-world datasets, our experimental results verify the effectiveness and efficiency of PDFC.

This paper proposes a federated, fair, and fast k-means algorithm (F3KM) to solve the fair clustering problem efficiently in scenarios where data cannot be shared among different parties. The proposed algorithm decomposes the fair k-means problem into multiple subproblems and assigns each subproblem to a client for local computation. Our algorithm allows each client to possess multiple sensitive attributes (or have no sensitive attributes). We propose an in-processing method that employs the alternating direction method of multipliers (ADMM) to solve each subproblem. During the procedure of solving subproblems, only the computation results are exchanged between the server and the clients, without exchanging the raw data. Our theoretical analysis shows that F3KM is efficient in terms of both communication and computation complexities. Specifically, it achieves a better trade-off between utility and communication complexity, and reduces the computation complexity to linear with respect to the dataset size. Our experiments show that F3KM achieves a better trade-off between utility and fairness than other methods. Moreover, F3KM is able to cluster five million points in one hour, highlighting its impressive efficiency.

In this paper, we would like to demonstrate a personal trajectory management system called Motorch, which allows users to manage their trajectories and enables risk analytics based on a lightweight similarity measure called LCTS. At the back end, a web crawler collects the desensitized COVID-19 cases information from data sources (news, social media, etc.) and pushes them to Elasticsearch for storage after data cleaning. At the front end, Motorch implements a set of operations including data collection, data preprocessing, indexing, storage, and visualization in a mobile application. Motorch aims to help individuals manipulate their data and evaluate personal risk without uploading data to a server.

The efficiency of query processing is highly affected by execution plans and allocated resources in the Spark SQL big data processing engine. However, the cost models for Spark SQL are still based on hand-crafted rules. The learning-based cost models have been proposed for relational databases, but it does not consider the effect of the available resources. To address this, we propose a resource-aware deep learning model that can automatically predict the execution time of query plans based on historical data. To train our model, we embed the query execution plans based on the query plan tree and extract features from the allocated resources. A deep learning model with adaptive attention mechanisms is then trained to predict the execution time of query plans. The experiments show that our deep cost model can achieve higher accuracy in predicting the execution time of query plans compared to traditional rule-based methods and relational database learning-based optimizers.

The amount of spatial data in open data portals has increased rapidly, raising the demand for spatial dataset search in large data repositories. In this paper, we tackle spatial dataset search by using the Earth Mover's Distance (EMD) to measure the similarity between datasets. EMD is a robust similarity measure between two distributions and has been successfully applied to multiple domains such as image retrieval, document retrieval, multimedia, etc. However, the existing EMD-based studies typically depend on a common filtering framework with a single pruning strategy, which still has a high search cost. To address this issue, we propose a Dual-Bound Filtering (DBF) framework to accelerate the EMD-based spatial dataset search. Specifically, we represent datasets by Z-order histograms and organize them as nodes in a tree structure. During a query, two levels of filtering are conducted based on pooling-based bounds and a TICT bound on EMD to prune dissimilar datasets efficiently. We conduct experiments on four real-world spatial data repositories and the experimental results demonstrate the efficiency and effectiveness of our DBF framework.

In this paper, we make a first attempt to incorporate both commuting demand and transit network connectivity in bus route planning (CT-Bus), and formulate it as a constrained optimization problem: planning a new bus route with k edges over an existing transit network without building new bus stops to maximize a linear aggregation of commuting demand and connectivity of the transit network. We prove the NP-hardness of CT-Bus and propose an expansion-based greedy algorithm that iteratively scans potential candidate paths in the network. To boost the efficiency of computing the connectivity of new networks with candidate paths, we convert it to a matrix trace estimation problem and employ a Lanczos method to estimate the natural connectivity of the transit network with a guaranteed error bound. Furthermore, we derive upper bounds on the objective values and use them to greedily select candidates for expansion. Our experiments conducted on real-world transit networks in New York City and Chicago verify the efficiency, effectiveness, and scalability of our algorithms.

This paper presents a thorough evaluation of the existing methods that accelerate Lloyd's algorithm for fast k -means clustering. To do so, we analyze the pruning mechanisms of existing methods, and summarize their common pipeline into a unified evaluation framework UniK. UniK embraces a class of well-known methods and enables a fine-grained performance breakdown. Within UniK, we thoroughly evaluate the pros and cons of existing methods using multiple performance metrics on a number of datasets. Furthermore, we derive an optimized algorithm over UniK, which effectively hybridizes multiple existing methods for more aggressive pruning. To take this further, we investigate whether the most efficient method for a given clustering task can be automatically selected by machine learning, to benefit practitioners and researchers.

In this paper, we would like to demonstrate an intelligent traffic analytics system called T4, which enables intelligent analytics over real-time and historical trajectories from vehicles. At the front end, we visualize the current traffic flow and result trajectories of different types of queries, as well as the histograms of traffic flow and traffic lights. At the back end, T4 is able to support multiple types of common queries over trajectories, with compact storage, efficient index and fast pruning algorithms. The output of those queries can be used for further monitoring and analytics purposes. Moreover, we train the deep models for traffic flow prediction and traffic light control to reduce traffic congestion. A preliminary version of T4 is available at https://sites.google.com/site/shengwangcs/torch.

In this paper, we study the problem of large-scale trajectory data clustering,k-paths, which aims to efficiently identifyk"representative" paths in a road network. Unlike traditional clustering approaches that require multiple data-dependent hyperparameters,k-paths can be used for visual exploration in applications such as traffic monitoring, public transit planning, and site selection. By combining map matching with an efficient intermediate representation of trajectories and a noveledge-based distance(EBD) measure, we present a scalable clustering method to solvek-paths. Experiments verify that we can cluster millions of taxi trajectories in less than one minute, achieving improvements of up to two orders of magnitude over state-of-the-art solutions that solve similar trajectory clustering problems.

We study a new kind of query - a Reverse k Nearest Neighbor Search over Trajectories (RkNNT), which can be used for route planning and capacity estimation in the transportation field. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an RkNNT query returns all transitions that take Q as one of its k nearest travel routes. We develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data is available for answering an RkNNT query using a filter-refine processing framework. Further, an application of using RkNNT to plan the optimal route in bus networks, namely MaxRkNNT, is proposed and studied. Experiments on real datasets demonstrate the efficiency and scalability of our approaches. In the future, the RkNNT can be extended to applied to the traffic prediction.

This paper presents a new trajectory search engine called Torch for querying road network trajectory data. Torch is able to efficiently process two types of typical queries (similarity search and Boolean search), and support a wide variety of trajectory similarity functions. Additionally, we propose a new similarity function LORS in Torch to measure the similarity in a more effective and efficient manner. Indexing and search in Torch works as follows. First, each raw vehicle trajectory is transformed to a set of road segments (edges) and a set of crossings (vertices) on the road network. Then a lightweight edge and vertex index called LEVI is built. Given a query, a filtering framework over LEVI is used to dynamically prune the trajectory search space based on the similarity measure imposed. Finally, the result set (ranked or Boolean) is returned. Extensive experiments on real trajectory datasets verify the effectiveness and efficiency of Torch.

In this paper, we build a trip planning system called TISP, which enables user's interactive exploration of POIs and trajectories in their incremental trip planning. At the back end, TISP is able to support seven types of common queries over spatial-only, spatial-textual and textual-only data, based on our proposed unified indexing and search paradigm [7]. At the front end, we propose novel visualisation designs to present the result of different types of queries; our user-friendly interaction designs allow users to construct further queries without inputting any text.

This paper studies the location-based web search and aims to build a unified processing paradigm for two purposes: (1) efficiently support each of the various types of location-based queries (kNN query, top-k spatial-textual query, etc.) on two major forms of geo-tagged data, i.e., spatial point data such as geo-tagged web documents, and spatial trajectory data such as a sequence of geo-tagged travel blogs by a user; (2) support interactive search to provide quick response for a query session, within which a user usually keeps refining her query by either issuing different query types or specifying different constraints (e.g., adding a keyword and/or location, changing the choice of k, etc.) until she finds the desired results. To achieve this goal, we first propose a general Top-k query called Monotone Aggregate Spatial Keyword query-MASK, which is able to cover most types of location-based web search. Next, we develop a unified indexing (called Textual-Grid-Point Inverted Index) and query processing paradigm (called ETAIL Algorithm) to answer a single MASK query efficiently. Furthermore, we extend ETAIL to provide interactive search for multiple queries within one query session, by exploiting the commonality of textual and/or spatial dimension among queries. Last, extensive experiments on four real datasets verify the robustness and efficiency of our approach.

GPS enables mobile devices to continuously provide new opportunities to improve our daily lives. For example, the data collected in applications created by Uber or Public Transport Authorities can be used to plan transportation routes, estimate capacities, and proactively identify low coverage areas. In this paper, we study a new kind of query-Reverse k Nearest Neighbor Search over Trajectories (RkNNT), which can be used for route planning and capacity estimation. Given a set of existing routes DR, a set of passenger transitions DT, and a query route Q, an RkNNT query returns all transitions that take Q as one of its k nearest travel routes. To solve the problem, we first develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data are available for answering an RkNNT query. Then we introduce a filter refinement framework for processing RkNNT queries using the proposed indexes. Next, we show how to use RkNNT to solve the optimal route planning problem MaxRkNNT (MinRkNNT), which is to search for the optimal route from a start location to an end location that could attract the maximum (or minimum) number of passengers based on a predefined travel distance threshold. Experiments on real datasets demonstrate the efficiency and scalability of our approaches. To the best of our knowledge, this is the first work to study the RkNNT problem for route planning.

We study a new type of spatial-textual trajectory search: the Exemplar Trajectory Query (ETQ), which specifies one or more places to visit, and descriptions of activities at each place. Our goal is to efficiently find the top-k trajectories by computing spatial and textual similarity at each point. The computational cost for pointwise matching is significantly higher than previous approaches. Therefore, we introduce an incremental pruning baseline and explore how to adaptively tune our approach, introducing a gap-based optimization and a novel twolevel threshold algorithm to improve efficiency. Our proposed methods support order-sensitive ETQ with a minor extension. Experiments on two datasets verify the efficiency and scalability of our proposed solution.