Author name cluster

Ninh Pham

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

AAAI Conference 2025 Conference Paper

On Finding Hubs in High Dimensions with Sampling

Huiwen Dong
Linghan Zeng
Zhiwen Zhao
Francesco Silvestri
Ninh Pham

Hubs are a few points that frequently appear in the k-nearest neighbors (kNN) of many other points in a high-dimensional data set. The hubs' effects, called the hubness phenomenon, degrade the performance of kNN based models in high dimensions. We present SamHub, a simple sampling approach to efficiently identify hubs with theoretical guarantees. Apart from previous works based on approximate kNN indexes, SamHub is generic and applicable to any distance measure with negligible additional memory footprint. Empirically, by sampling only 10% of points, SamHub runs significantly faster and offers higher accuracy than existing hub detection methods on many real-world data sets with dot product, L1, L2, and dynamic time warping distances. Our ablation studies of SamHub on improving kNN-based classification show potential for other high-dimensional data analysis tasks.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Scalable DBSCAN with Random Projections

HaoChuan Xu
Ninh Pham

We present sDBSCAN, a scalable density-based clustering algorithm in high dimensions with cosine distance. sDBSCAN leverages recent advancements in random projections given a significantly large number of random vectors to quickly identify core points and their neighborhoods, the primary hurdle of density-based clustering. Theoretically, sDBSCAN preserves the DBSCAN’s clustering structure under mild conditions with high probability. To facilitate sDBSCAN, we present sOPTICS, a scalable visual tool to guide the parameter setting of sDBSCAN. We also extend sDBSCAN and sOPTICS to L2, L1, χ2, and Jensen-Shannon distances via random kernel features. Empirically, sDBSCAN is significantly faster and provides higher accuracy than competitive DBSCAN variants on real-world million-point data sets. On these data sets, sDBSCAN and sOPTICS run in a few minutes, while the scikit-learn counterparts and other clustering competitors demand several hours orcannot run on our hardware due to memory constraints. Our code is available at https: //github. com/NinhPham/sDbscan.

PDF Details DOI

NeurIPS Conference 2022 Conference Paper

Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search

Ninh Pham
Tao Liu

We present Falconn++, a novel locality-sensitive filtering (LSF) approach for approximate nearest neighbor search on angular distance. Falconn++ can filter out potential far away points in any hash bucket before querying, which results in higher quality candidates compared to other hashing-based solutions. Theoretically, Falconn++ asymptotically achieves lower query time complexity than Falconn, an optimal locality-sensitive hashing scheme on angular distance. Empirically, Falconn++ achieves a higher recall-speed tradeoff than Falconn on many real-world data sets. Falconn++ is also competitive with HNSW, an efficient representative of graph-based solutions on high search recall regimes.

PDF Details

IJCAI Conference 2021 Conference Paper

Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search (Extended Abstract)

Stephan S. Lorenzen
Ninh Pham

Top-k maximum inner product search (MIPS) is a central task in many machine learning applications. This work extends top-k MIPS with a budgeted setting, that asks for the best approximate top-k MIPS given a limited budget of computational operations. We study recent advanced sampling methods, including wedge and diamond sampling, to solve budgeted top-k MIPS. First, we theoretically show that diamond sampling is essentially a combination of wedge sampling and basic sampling for top-k MIPS. Second, we propose dWedge, a simple deterministic variant of wedge sampling for budgeted top-k MIPS. Empirically, dWedge provides significantly higher accuracy than other budgeted top-k MIPS solvers while maintaining a similar speedup.

PDF Details DOI