Private Set Intersection (PSI) enables parties to compute the intersection of their input sets while preserving privacy. While most PSI protocols are designed for balanced scenarios with sets of similar sizes, unbalanced PSI addresses situations where a server with a large database (e.g., millions of records) performs PSI with multiple clients, each with a set of only a few hundred elements. In this scenario, it is desirable for the server's computation on its large set to be performed offline and reusable, which we refer to as the "Client-Independent" property. However, existing offline/online unbalanced PSI protocols rely on less efficient OPRF constructions, which involve either computationally expensive exponential operations or communication-intensive garbled circuits. In this work, we present a framework for offline/online unbalanced PSI, with its core component being a novel functionality called "Client-Independent Relaxed OPRF" (ci-rOPRF). The key insight behind ci-rOPRF is to capture the requirements for OPRF in offline/online scenarios. To realize this functionality, we propose two constructions of ci-rOPRF, inspired by the top-performing CM-OPRF (CRYPTO '20) and VOLE-OPRF (EUROCRYPT '21), respectively. Leveraging these efficient ci-rOPRF constructions, we design highly efficient offline/online unbalanced PSI protocols. Furthermore, we extend this framework with two enhancements: one supports set updates, while the other reduces offline communication costs. Our C++ implementation demonstrates highly efficient performance. For instance, in the online phase, our fastest unbalanced PSI protocol computes the intersection of a client set with 2^12 elements and a server set with 2^28 elements in just 0.55 seconds and 0.62 MiB of communication on a 100 Mbps WiFi connection. Comparisons with state-of-the-art unbalanced PSI protocols show that our protocols significantly outperform existing solutions in the semi-honest model on most metrics.

We present an efficient and simple multi-party private set intersection cardinality (PSI-CA) protocol that allows several parties to learn the intersection size of their private sets without revealing any other information. Our protocol is highly efficient because it only utilizes the Oblivious Key-Value Store and zero-sharing techniques, without incorporating components such as OPPRF (Oblivious Programmable Pseudorandom Function) which is the main building block of multi-party PSI-CA protocol by Gao et al. (PoPETs 2024). Our protocol exhibits better communication and computational overhead than the state-ofthe-art. To compute the intersection between 16 parties with a set size of 220each, our PSI-CA protocol only takes 5.84 seconds and 326.6 MiB of total communication, which yields a reduction in communication by a factor of up to 2.4× compared to the state-of-the-art multi-party PSI-CA protocol of Gao et al. (PoPETs 2024). We prove that our protocol is secure in the presence of a semi-honest adversary who may passively corrupt any (t−2)-out-of-t parties once two specific participants are non-colluding.

Graph neural networks (GNNs) have been widely used in various graph-related problems such as node classification and graph classification, where the superior performance is mainly established when natural node features are available. However, it is not well understood how GNNs work without natural node features, especially regarding the various ways to construct artificial ones. In this paper, we point out the two types of artificial node features, i.e., positional and structural node features, and provide insights on why each of them is more appropriate for certain tasks, i.e., positional node classification, structural node classification, and graph classification. Extensive experimental results on 10 benchmark datasets validate our insights, thus leading to a practical guideline on the choices between different artificial node features for GNNs on non-attributed graphs. The code is available at https://github.com/zjzijielu/gnn-positional-structural-node-features.

Massive data streams from sensors in Internet of Things (IoT) and smart devices with Global Positioning System (GPS) are now flooding to database systems for further processing and analysis. The capability of real-time retrieval from both fresh and historical data turns out to be the key enabler to the real world applications in smart manufacturing and smart city utilizing these data streams. In this paper, we present a simple and effective distributed solution to achieve millions of tuple insertions per second and ad-hoc temporal range query processing in milliseconds. To this end, we propose a new data partitioning scheme that takes advantage of the workload characteristics and avoids expensive global data merging. Furthermore, to resolve the throughput bottleneck, we adopt a template-based index method to skip unnecessary index structure adjustments over the relatively stable distribution of incoming tuples. To parallelize data insertion and query processing, we propose an efficient dispatching mechanism and effective load balancing strategies to fully utilize computational resources in a workload-aware manner. On both synthetic and real workloads, our solution consistently outperforms state-of-the-art open-source systems by at least an order of magnitude.

The prosperity of mobile social network and location-based services, e.g., Uber, is backing the explosive growth of spatial temporal streams on the Internet. It raises new challenges to the underlying data store system, which is supposed to support extremely high-throughput trajectory insertion and low-latency querying with spatial and temporal constraints. State-of-the-art solutions, e.g., HBase, do not render satisfactory performance, due to the high overhead on index update. In this demonstration, we present DITIR, our new system prototype tailored to efficiently processing temporal and spacial queries over historical data as well as latest updates. Our system provides better performance guarantee, by physically partitioning the incoming data tuples on their arrivals and exploiting a template-based insertion schema, to reach the desired ingestion throughput. Load balancing mechanism is also introduced to DITIR, by using which the system is capable of achieving reliable performance against workload dynamics. Our demonstration shows that DITIR supports over 1 million tuple insertions in a second, when running on a 10-node cluster. It also significantly outperforms HBase by 7 times on ingestion throughput and 5 times faster on query latency.