Radius-bounded$k$-core queries (RB-$k$-core queries) in geo-social networks aim to identify all$k$-cores containing a given query vertex$q$, where all vertices in each$k$-core fall within a circle defined by a specified query radius$r$. These queries are widely used in applications such as team formation and event organization. However, specifying query parameters$k$and$r$can be challenging for users without domain expertise, often resulting in misaligned query results. Specifically, some expected vertices may be missing, while unexpected vertices may appear in the results. To address this issue, we investigate the problem ofexploringoptimalrefinedparametersforexpected(EOPE) andunexpected(EOPU) results in RB-$k$-core queries. The goal is to explore optimal parameters that ensure the expected vertex$\omega$(or unexpected vertex$\psi$) and query vertex$q$appear (or do not appear) in the same RB-$k$-core. For the EOPE problem, we first propose two baseline algorithms:PriorityRandHybridR. To improve efficiency, we develop two more advanced algorithms:PriorityKandHybridK. Additionally, we introduce a novel index calledHCR-Tree, based on hierarchical coreness of vertices and R-Tree, to enhance exploration efficiency. For the EOPU problem, we begin with a basic solution (BS) and then design the segmentation algorithmSA, which incorporates effective pruning and termination strategies. We conduct extensive experiments on five real-world geo-social network datasets. The results demonstrate that our proposed algorithms effectively explore optimal parameters. Among them,HybridKproves most effective for EOPE, whileSAperforms best for EOPU. Furthermore,HCR-Treeoutperforms R-Tree for both EOPE and EOPU problems.

Hybrid-storage blockchains have become a promising paradigm for scaling up query processing services. This paradigm provides a hybrid on/off-chain approach, where only small metadata is stored on-chain while the raw data is outsourced to off-chain storage. The key concerns for query processing in such a system are security and query integrity. However, existing schemes mostly address an impractical honest-but-curious model, rather than a more realistic malicious model, due to the intricate interplay between security and query integrity. Additionally, supporting efficient dynamic update with forward security is a significant challenge for blockchain systems. To address these issues, in this paper, we first formally define the problem of secure, reliably verifiable, and dynamic Boolean range queries in hybrid-storage blockchains (SRVF). Then, we propose a novel index called Virtual Keyword Forest (VKF), which achieves secure and reliably verifiable query processing in hybrid-storage blockchains. To support dynamic queries with forward security, we propose an adaptive version-control update scheme to integrate into VKF. Furthermore, to reduce communication overhead and gas consumption, we design an aggregation signature algorithm that ensures the verification information is of a fixed size. We provide theoretical security analysis and empirical evaluations, comparing our proposed approaches with the state-of-the-art approaches, to demonstrate their feasibility.

A corpus of recent work has revealed that authenticated query services have been under the spotlight due to the untrustworthiness of outsourced service provider. To enrich scalable functionality, there is an increasing demand for dynamically authenticated query. However, when implementing query and update simultaneously, traditional approaches heavily suffer from the inconsistency between verification digest and requested index and therefore are infeasible in reality. Moreover, the efficiency of storage, query, verification, and update is still a huge hinder when processing large scale data. To address these challenging issues, in this paper, we propose a novel idea of authenticated learned index that is carefully designed and actively optimized for authenticated query processing. Specifically, we first propose a version control update mechanism for consistency guarantee by maintaining historical index versions. Following this, we propose two basic authenticated learned indexes, i.e., query-friendly PVL-tree and update-friendly PVLB-tree, to support efficient scalable authenticated range query. Furthermore, to improve the efficiency, we introduce a hybrid index framework HPVL-tree based on two basic indexes. Extensive theoretical and experimental analysis demonstrate that our proposed HPVL-tree outperforms the state-of-the-art approaches by up to$2.28\times, 3.96\times$, and$2.51\times$in search time, update time, and verification time, respectively. Moreover, the storage overhead and communication overhead occupy only 38 % and 2.25 % of existing approach, respectively.

A modern service model known as the “hub-oriented” model has emerged with the development of mobility services. This model allows users to request vehicles from multiple companies (agents) simultaneously through a unified entry (a ‘hub’). In contrast to conventional services, the “hub-oriented” model emphasizes pricing competition. To address this scenario, an agent should consider its competitors when developing its pricing strategy. In this paper, we introduce DRLPG, a mixed opponent-aware pricing method, which consists of two main components: the two-stage guarantor and the end-to-end deep reinforcement learning (DRL) module, as well as interaction mechanisms. In the guarantor, we design a prediction-decision framework. Specifically, we propose a new objective function for the spatiotemporal neural network in the prediction stage and utilize a traditional reinforcement learning method in the decision stage, respectively. In the end-to-end DRL framework, we explore the adoption of conventional DRL in the “hub-oriented” scenario. Finally, a meta-decider and an experience-sharing mechanism are proposed to combine both methods and leverage their advantages. We conduct extensive experiments on real data, and DRLPG achieves an average improvement of 99.9% and 61.1% in the peak and low peak periods, respectively. Our results demonstrate the effectiveness of our approach compared to the baseline.

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. Finally, we provide empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed scheme.

Radius-bounded$k$-core queries (RB-$k$-core queries) in geo-social networks aim to find all$k$-cores containing a given query vertex$q$while all vertices in each$k$-core fall into a circle under a given query radius$r$, which is widely used in many applications, such as team formulation and event organization. However, the query parameters$k$and$r$are hard to specify by the users without any background knowledge, which means the query results often do not meet the users' requirements, i.e., some expected vertices are missed in the query results. To tackle this issue, we investigate the problem of exploring optimal refined parameters (EOP) for expected results on RB­$k$-core queries, which aims to explore the optimal parameters that make the expected vertex$\omega$and query vertex$q$appear in the same RB-$k$-core. To address the EOP problem, we first propose two baseline algorithms, namely PriorityR and HybridR, which refine the parameters$k$and$r$simultaneously based on the effective bounds of the refined$r^{\prime}$• To enhance the efficiency of exploring optimal parameters, we develop two efficient al-gorithms. The first algorithm, Priority K, simultaneously refines both parameters based on the effective bound of the refined$k$• The second algorithm, HybridK, explores the optimal parameters using the continuous convergence bounds of the refined$k^{\prime}$and$r$• Furthermore, to enhance exploration efficiency, we develop a novel index, called HCR-Tree, based on the hierarchical coreness of vertices and R- Tree. This index accelerates the verification of whether the coreness of a vertex in any sub graph exceeds$k$in the above algorithms. Finally, we conduct extensive experiments using five real geo-social network datasets, which show that the optimal parameters can be explored effectively by the algorithms, and HybridK is the most effective. Meanwhile, the HCR- Tree performs better than the R- Tree for the EOP problem.

Due to the easy access, implicit feedback is often used for recommender systems. Compared with point-wise learning and pair-wise learning methods, list-wise rank learning methods have superior performance for top- \(N\) recommendation. Recent solutions, especially the list-wise methods, simply treat all interacted items of a user as equally important positives and annotate all no-interaction items of a user as negatives. For the list-wise approaches, we argue that this annotation scheme of implicit feedback is over-simplified due to the sparsity and missing fine-grained labels of the feedback data. To overcome this issue, we revisit the so-called positive and negative samples. First, considering the loss function of list-wise ranking, we analyze the impact of false positives and negatives theoretically. Second, based on the observation, we propose a self-adjusting credibility weight mechanism to re-weigh the positive samples and exploit the higher-order relation based on item–item matrix to sample the critical negative samples. In order to prevent the introduction of noise, we design a pruning strategy for critical negatives. Besides, to combine the reconstruction loss function for the positive samples and critical negative samples, we develop a simple yet effective VAEs framework with linear structure, which abandons the complex non-linear structure. Extensive experiments are conducted on six public real-world datasets. The results demonstrate that, our VAE* outperforms other VAE-based models by a large margin. Besides, we also verify the effect of denoising positives and exploring critical negatives by ablation study.

Blockchain has emerged as a prevailing paradigm for decentralized applications due to its reliability and transparency. To scale up retrieval services, a common strategy is to use a hybrid storage model, where on-chain storage is responsible for small metadata and off-chain storage is for outsourced raw data. However, data security and result authenticity are ongoing challenges in this scenario, and little work has been done due to the difficulty of combining result verification and privacy preservation, especially for dynamic updates while supporting forward privacy. In this paper, we formally define the problem of efficient, verifiable, and secure conjunctive keyword search in hybrid-storage blockchains (vsChain) and propose a novel hybrid index that achieves efficient query and verification while supporting dynamic updates with forward privacy guarantee. We also design two optimized schemes to improve query and verification performance by using a partition-based method and an obfuscated counting Bloom filter mechanism. Finally, we provide a theoretical security analysis and empirical evaluations using real and synthetic datasets to demonstrate the feasibility of our proposed schemes.

Data outsourcing to the cloud has become increasingly popular for high-speed storage and retrieval. However, privacy and security are pressing concerns that hinder the further development of cloud computing. A common approach is to encrypt data before outsourcing, assuming the cloud is semi-honest. However, in reality, the cloud may be malicious and forge query results unexpectedly. Moreover, most previous schemes are designed for single-user setting, where different users share the same secret key, leading to potential privacy leaks. Therefore, ensuring confidentiality and verifiability in multi-user setting is crucial but has not been well-addressed. In this paper, we formally define the notion of Verifiable and Secure Range Query in Multi-User Setting (VSRQM) and propose a prefix-aware encoding (Pcode) scheme to encode spatial data for query processing. Next, we design a Tree-Aided Verifiable and Secure Index (SATree) on top of the Pcode and symmetric re-encryption scheme. SATree preserves data privacy, provides a mechanism to verify query results’ integrity and achieves sub-linear search time. Additionally, we propose two compression schemes to reduce the space cost of storage and transmission. Finally, we present formal complexity and security analyses and conduct empirical evaluations on real and synthetic datasets to demonstrate our proposed approaches’ practical performance.

Hub-oriented mobility services have gained great developments in recent years, enabling riders to simultaneously call vehicles from multiple mobility-supply companies (agents) on a single APP (which we call "hub"). Competing with others on such a hub, to obtain an order, an agent company first needs to get admitted by the requester, which is in turn affected by its quotation. The quotation needs to be attractively low compared to those of the opposing agents. Thus, an opponent-aware pricing strategy is needed for an agent to play well in the hub scenario, which is rarely discussed in existing works. To address the aforementioned issue, in this work, we first propose a quotation prediction model, which employs a neural network with a customized loss function to predict the opponents’ quotations. Based on the predictions, we then propose multi-arm bandit based methods to decide a proper quotation for the agent, in order to obtain orders while retaining profits. We finally conduct extensive experiments on real data, where the quotation-determining method integrated with the prediction model has achieved a remarkable profit improvement up to 85.5% compared to baseline methods, demonstrating their effectiveness.

Socially tenuous groups (or simply tenuous groups) in a social network/graph refer to subgraphs with few social interactions and weak relationships among members. However, existing studies on tenuous group queries do not consider the user profiles (keywords) of the members whereas in many social network applications, e.g., finding reviewers for paper selection and recommending seed users in social advertising, keywords also need to be considered. Thus, in this paper, we investigate the problem of keywords-based socially tenous group (KTG) queries. A KTG query is to find top N tenuous groups in which the members of each group jointly cover the most number of query keywords. To address the KTG problem, we first propose two exact algorithms, namely KTG-VKC and KTG-VKC-DEG, which give priority to the valid keyword coverage and the combination of valid keyword coverage and degree, respectively, to select members to form a feasible group by adopting a branch and bound (BB) strategy. Moreover, we propose keyword pruning and k-line filtering to accelerate the algorithms. To yield diversified KTG results, we also study the problem of diversified keywords-based socially tenous group (DKTG) queries. To deal with the DKTG problem, we propose a DKTG-Greedy algorithm by exploiting a greedy heuristic in combination with KTG-VKC-DEG. Furthermore, we design two alternative indexes, namely NL and NLRNL, to efficiently check whether the social distance of any two members is greater than the social constraint k in the above algorithms. We conduct extensive experiments using real datasets to validate our ideas and evaluate the proposed algorithms. Experimental results show that the NLRNL index achieves a better performance than the NL index.

Geo-social groupqueries, which return a social cohesive user group with a spatial constraint, have receive significant research interests due to their promising applications for group-based activity planning and scheduling in location-based social networks (LBSNs). However, existing studies on geo-social group queries mostly assume the users are stationary whereas in realistic LBSN application scenarios all users may continuously move over time. Thus, in this paper, we investigate the problem ofcontinuousgeo-socialgroupsmonitoring(CGSGM) over moving users. A challenge in answering CGSGM queries over moving users is how to efficiently update geo-social groups when users are continuously moving. To address the CGSGM problem, we first propose a baseline algorithm, namelyBaseline-BB, which recomputes the new geo-social groups from scratch at each time instance by utilizing a branch and bound (BB) strategy. To improve the inefficiency of BB, we explore a new strategy, called common neighbor or neighbor expanding (CNNE), which expands the common neighbors of edges or the neighbors of users in intermediate groups to quickly produce the valid group combinations. Accordingly, another baseline algorithm, namelyBaseline-CNNE, is proposed. As these baseline algorithms do not maintain intermediate results to facilitate further query processing, we develop an incremental algorithm, calledincremental monitoring algorithm (IMA), which maintains the support, common neighbors and the neighbors of current users when exploring possible user groups for further updates and query processing. Since IMA requires many times of truss decomposition when processing mutiple-users updates, we propose an improved incremental algorithm, calledimproved incremental monitoring algorithm (IIMA), which performs truss decompostion only once. Moreover, we design algorithms for handling the social changes that result in insertion/deletion of some edges in the social network. Owing to the challenge in setting, an appropriate monitoring distance, we further study the top$N$CGSGM problem, which finds top$N$result groups at each time instance. Finally, we conduct extensive experiments using four real datasets to validate our ideas and evaluate the proposed algorithms.

Recently a lot of research works have focused on geo-social group queries for group-based activity planning and scheduling in location-based social networks (LBSNs), which return a social cohesive user group with a spatial constraint. However, existing studies on geo-social group queries assume the users are stationary whereas in real LBSN applications all users may continuously move over time. Thus, in this paper we in-vestigate the problem of continuous geo-social groups monitoring (CGSGM) over moving users. A challenge in answering CGSGM queries over moving users is how to efficiently update geo-social groups when users are continuously moving. To address the CGSGM problem, we first propose a baseline algorithm, namely Baseline-BB, which recomputes the new geo-social groups from scratch at each time instance by utilizing a branch and bound (BB) strategy. To improve the inefficiency of BB, we propose a new strategy, called common neighbor or neighbor expanding (CNNE), which expands the common neighbors of edges or the neighbors of users in intermediate groups to quickly produce the valid group combinations. Based on CNNE, we propose another baseline algorithm, namely Baseline-CNNE. As these baseline algorithms do not maintain any intermediate results to facilitate further query processing, we develop an incremental algorithm, called incremental monitoring algorithm (IMA), which maintains the support, common neighbors and the neighbors of current users when exploring possible user groups for further updates and query processing. Finally, we conduct extensive experiments using three real datasets to validate our ideas and evaluate the proposed algorithms,

Abstract The optimal sequenced route (OSR) query, as a popular problem in route planning for smart cities, searches for a minimum-distance route passing through several POIs in a specific order from a starting position. In reality, POIs are usually rated, which helps users in making decisions. Existing OSR queries neglect the fact that the POIs in the same category could have different scores, which may affect users’ route choices. In this paper, we study a novel variant of OSR query, namely Rating Constrained Optimal Sequenced Route query (RCOSR), in which the rating score of each POI in the optimal sequenced route should exceed the query threshold. To efficiently process RCOSR queries, we first extend the existing TD-OSR algorithm to propose a baseline method, called MTDOSR. To tackle the shortcomings of MTDOSR, we try to design a new RCOSR algorithm, namely Optimal Subroute Expansion (OSE) Algorithm. To enhance the OSE algorithm, we propose a Reference Node Inverted Index (RNII) to accelerate the distance computation of POI pairs in OSE and quickly retrieve the POIs of each category. To make full use of the OSE and RNII, we further propose a new efficient RCOSR algorithm, called Recurrent Optimal Subroute Expansion (ROSE), which recurrently utilizes OSE to compute the current optimal route as the guiding path and update the distance of POI pairs to guide the expansion. Then, we extend our techniques to handle a variation of RCOSR query, namely RCkOSR query. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.

Abstract Motivated by location-based social networks which allow people to access location-based services as a group, we study a novel variant of optimal sequenced route (OSR) queries, optimal sequenced route for group meetup (OSR-G) queries. OSR-G query aims to find the optimal meeting POI (point of interest) such that the maximum users’ route distance to the meeting POI is minimized after each user visits a number of POIs of specific categories (e.g., gas stations, restaurants, and shopping malls) in a particular order. To process OSR-G queries, we first propose an OSR-Based (OSRB) algorithm as our baseline, which examines every POI in the meeting category and utilizes existing OSR (called E-OSR) algorithm to compute the optimal route for each user to the meeting POI. To address the shortcomings (i.e., requiring to examine every POI in the meeting category) of OSRB, we propose an upper bound based filtering algorithm, called circle filtering (CF) algorithm, which exploits the circle property to filter the unpromising meeting POIs. In addition, we propose a lower bound based pruning (LBP) algorithm, namely LBP-SP which exploits a shortest path lower bound to prune the unqualified meeting POIs to reduce the search space. Furthermore, we develop an approximate algorithm, namely APS, to accelerate OSR-G queries with a good approximation ratio. Finally the experimental results show that both CF and LBP-SP outperform the OSRB algorithm and have high pruning rates. Moreover, the proposed approximate algorithm runs faster than the exact OSR-G algorithms and has a good approximation ratio.

In this paper, we study a novel variant of obstructed nearest neighbor queries, namely,range-based obstructed nearest neighbor(RONN) search. As a natural generalization ofcontinuous obstructed nearest-neighbor(CONN), an RONN query retrieves a set ofobstructed nearest neighborscorresponding to every point in a specified range. We propose a new index, namely binary obstructed tree (calledOB-tree), for indexing complex objects in the obstructed space. The novelty of OB-tree lies in the idea ofdividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an algorithm for construction of the OB-tree and propose a space division scheme, calledoptimal obstacle balance(OOB2) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, calledRONN by OB-tree Acceleration(RONN-OBA), which exploits the OB-tree and a binary traversal order of data objects to accelerate query processing of RONN. In addition, we extend our work in several aspects regarding the shape of obstacles, and range-based$k$NN queries in obstructed space. At last, we conduct a comprehensive performance evaluation using both real and synthetic datasets to validate our ideas and the proposed algorithms. The experimental result shows that the RONN-OBA algorithm outperforms the two R-tree based algorithms and RONN-OA significantly.

In this paper, we study a novel variant of obstructed nearest neighbor queries, namely, range-based obstructed nearest neighbor (RONN) search. A natural generalization of continuous obstructed nearest-neighbor (CONN), an RONN query retrieves the obstructed nearest neighbor for every point in a specified range. To process RONN, we first propose a CONN-Based (CONNB) algorithm as our baseline, which reduces the RONN query into a range query and four CONN queries processed using an R-tree. To address the shortcomings of the CONNB algorithm, we then propose a new RONN by R-tree Filtering (RONN-RF) algorithm, which explores effective filtering, also using R-tree. Next, we propose a new index, called O-tree, dedicated for indexing objects in the obstructed space. The novelty of O-tree lies in the idea of dividing the obstructed space into non-obstructed subspaces, aiming to efficiently retrieve highly qualified candidates for RONN processing. We develop an O-tree construction algorithm and propose a space division scheme, called optimal obstacle balance (OOB) scheme, to address the tree balance problem. Accordingly, we propose an efficient algorithm, called RONN by O-tree Acceleration (RONN-OA), which exploits O-tree to accelerate query processing of RONN. In addition, we extend O-tree for indexing polygons. At last, we conduct a comprehensive performance evaluation using both real and synthetic datasets to validate our ideas and the proposed algorithms. The experimental result shows that the RONN-OA algorithm outperforms the two R-tree based algorithms significantly. Moreover, we show that the OOB scheme achieves the best tree balance in O-tree and outperforms two baseline schemes.