Bipartite graphs are widely used in many real-world applications, where discovering clusters is crucial for understanding their underlying structure. However, most existing clustering methods for bipartite graphs enforce the assignment ofallvertices to clusters, often neglecting the important roles of outliers and hubs. To address this limitation, we plan to extend the structural clustering model from unipartite to bipartite graphs. This extension is non-trivial due to the lack of common neighbors in bipartite graphs, which renders traditional similarity measures less effective. Recognizing that similarity is key to structural clustering, we resort to butterflies—the fundamental building blocks of bipartite graphs—to define a more effective similarity measure. Building on this, we further propose a novel structural clustering model, SBC, tailored for bipartite graphs. To enable clustering under this model, we develop efficient online and index-based methods, along with a dynamic maintenance method to accommodate graph updates over time. Extensive experiments on real-world bipartite graphs demonstrate that: (1) The SBC model greatly enhances clustering quality, achieving higher modularity while effectively identifying outliers and hubs. (2) Our proposed clustering methods are highly scalable, enabling the processing of graphs with up to 12.2 million edges within 2 seconds

Approximate K Nearest Neighbor (AKNN) search in high-dimensional spaces is a critical yet challenging problem. In AKNN search, distance computation is the core task that dominates the runtime. Existing approaches typically use approx-imate distances to improve computational efficiency, often at the cost of reduced search accuracy. To address this issue, the state-of-the-art method, ADSampling, employs random projections to estimate approximate distances and introduces an additional distance correction process to mitigate accuracy loss. However, ADSampling has limitations in both effectiveness and generality, primarily due to its heavy reliance on random projections for distance approximation and correction. Motivated by this, we leverage data distribution to improve distance approximation via orthogonal projection, thereby ad-dressing the effectiveness limitation of ADSampling; we also adopt a data-driven approach to distance correction, decoupling the correction process from the distance approximation process, thereby overcoming the generality limitation of ADSampling. Ex-tensive experiments demonstrate the superiority and effectiveness of our method. In particular, compared to ADSampling, our method achieves a speedup of 1.6 to 2.1 times on real-world datasets while providing higher accuracy. In addition, our method shows superior performance in Ant Group image search scenarios and has been integrated into their search engine.

Approximate nearest neighbor search (ANNS) is a fundamental problem in vector databases and AI infrastructures. Recent graph-based ANNS algorithms have achieved high search accuracy with practical efficiency. Despite the advancements, these algorithms still face performance bottlenecks in production, due to the random memory access patterns of graph-based search and the high computational overheads of vector distance. In addition, the performance of a graph-based ANNS algorithm is highly sensitive to parameters, while selecting the optimal parameters is cost-prohibitive, e.g., manual tuning requires repeatedly re-building the index. This paper introduces VSAG , an open-source framework that aims to enhance the in production performance of graph-based ANNS algorithms. VSAG has been deployed at scale in the services of Ant Group, and it incorporates three key optimizations: ( i) efficient memory access : it reduces L3 cache misses with pre-fetching and cache-friendly vector organization; ( ii) automated parameter tuning : it automatically selects performance-optimal parameters without requiring index rebuilding; ( iii) efficient distance computation : it leverages modern hardware, scalar quantization, and smartly switches to low-precision representation to dramatically reduce the distance computation costs. We evaluate VSAG on real-world datasets. The experimental results show that VSAG achieves the state-of-the-art performance and provides up to 4× speedup over HNSWlib (an industry-standard library) while ensuring the same accuracy.

In real-world road networks, edges possess additional numeric attributes, such as width and toll, in addition to length. Incorporating these additional attributes enhances the functionality of shortest-distance services. To this end, current research on shortest-distance computation requires that the numeric attributes of edges on a path exceed a lower bound$l$(within the interval [l,oo]). However, it often overlooks the benefits of setting an upper bound$r$(within the interval [l, r]). To bridge this gap, we introduce the numeric-constrained shortest-distance query problem, which enforces interval constraints [l, r] on the numeric attributes of edges on a path. There are two intuitive solutions: the Online-Search method, which excludes edges that violate the constraints during the search, leading to inefficient query responses, and the Full-Index method, which creates an index for each necessary interval constraint [l, r], resulting in excessive space consumption due to numerous potential intervals. Our novel index-based method, which uses the tree decomposition technique and exploits interval-distance relationships, aims to mitigate these issues. As confirmed by our experimental results, our method greatly improves query speed - over 20 times faster than Online-Search- and consumes less space than Full-Index.