# DSI-3D: Differentiable Search Index for Point Cloud Retrieval

Chahine-Nicolas Zede, Laurent Caraffa, Valérie Gouet-Brunet

► To cite this version:

Chahine-Nicolas Zede, Laurent Caraffa, Valérie Gouet-Brunet. DSI-3D: Differentiable Search Index for Point Cloud Retrieval. 22nd International Conference on Content-Based Multimedia Indexing (CBMI'25), Oct 2025, Dublin, Ireland. hal-05345963

HAL Id: hal-05345963

https://hal.science/hal-05345963v1

Submitted on 4 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
DSI-3D: DIFFERENTIABLE SEARCH INDEX
FOR POINT CLOUDS RETRIEVAL

Chahine-Nicolas Zede

Laurent Caraffa

Valérie Gouet-Brunet

LASTIG

LASTIG

LASTIG

IGN-ENSG, Gustave Eiffel University

IGN-ENSG, Gustave Eiffel University

IGN-ENSG, Gustave Eiffel University

77420 Champs-sur-Marne, France

77420 Champs-sur-Marne, France

77420 Champs-sur-Marne, France

chahine-nicolas.zede@ign.fr

laurent.caraffa@ign.fr

valerie.gouet@ign.fr

**Abstract**—Retrieval in 3D point clouds is a challenging task that consists in retrieving the most similar point clouds to a given query within a reference of 3D points. Current methods focus on comparing descriptors of point clouds in order to identify similar ones, without any particular index structure. Due to the complexity of this latter step, here we focus on the acceleration of the retrieval by adapting the Differentiable Search Index (DSI), a transformer-based approach initially designed for text information retrieval, for 3D point cloud retrieval. Our approach generates 1D identifiers based on the point descriptors, enabling direct retrieval in constant time. To adapt DSI to 3D data, we integrate Vision Transformers to map descriptors to these identifiers while incorporating positional and semantic encoding. The approach is evaluated for place recognition on a public benchmark comparing its retrieval capabilities against state-of-the-art methods, in terms of quality and speed of returned point clouds.

**Index Terms**—3D retrieval, Scalable retrieval, 3D point cloud descriptors, Differentiable Search Index, LiDAR-based place recognition

# I. INTRODUCTION

Without any initial information on geolocation, the process of geolocalization from visual content typically begins with content-based indexing and retrieval [5]. In this work, we exploit 3D point clouds data, potentially obtained from LiDAR sensors, Structure-from-Motion or photogrammetry. This increasingly popular type of data is able to map scenes at large scale and thus serving as a reference, for geolocalization and mobile mapping or territory understanding purposes for example.

In this context, the article focuses on 3D point clouds retrieval, which involves finding the most similar point clouds to a given query within a reference database of point clouds. Research on retrieval within point clouds is still in its early stages. Existing solutions mainly focus on the indexing phase (i.e. generating point cloud descriptors) rather than on the retrieval phase, which aims to efficiently search similar descriptors in the reference. Current state of the art methods confirms that the main application of retrieval in point clouds is place recognition. Indeed, unlike image-based approaches, point clouds, relying on LiDAR for instance, have the benefits

<figure><img src="image_2.png" /><figcaption>Fig. 1. Differentiable search index pipeline [20] adapted for 3D data retrieval using GIT architecture [24]. (a) Labeling step: for each input of the database (red point cloud), the text decoder learns to generate the label according to the encoded point cloud. (b) Retrieval: given a point cloud as a query (black point cloud), a beam search is performed by the text decoder to provide the *n* most probable solutions.</figcaption></figure>

of being invariant to lighting and weather conditions [12], making them particularly relevant for this purpose. This is an interesting research area, with numerous key applications: for instance, position correction of LiDAR-equipped smartphones in dense urban environments, where urban canyon reduces GNSS accuracy. Point cloud retrieval may also apply for digital twin updates between a reference point cloud and a new acquisition for land surveying or monitoring structural changes over time. This is also relevant for autonomous navigation, where loop closure detection plays a crucial role in reducing drift in Simultaneous Localization and Mapping (SLAM) systems [25]. This can extend to media verification, fact checking videos for example, by geolocating point clouds reconstructed from video (e.g. with Structure-From-Motion).

The main objective of the article is to contribute to the retrieval phase in the 3D point cloud dataset, by proposing a scalable retrieval method, facing the size of this dataset and the dimensionality of the descriptors. To sum up, we have chosen to explore the application of Differentiable Search Index (DSI) [20] methods, originally developed for Information Retrieval in large text corpora, to the domain of point clouds. DSI employs a single T5 (text-to-text transfer transformer) model to map string queries to relevant document identifiers (docids).

This work is supported by the French Ministry of the Armed Forces - Defence Innovation Agency (AID). It was performed using HPC resources from GENCI-IDRIS (Grant 2024-AD011014030R1).
To bridge the gap between the 3D point cloud queries and the textual input required for Information Retrieval, we explored existing Place Recognition methods, such as PointNetVLAD [21] and LoGG3D-Net [23]. These methods have shown promising results in loop detection by encoding a point cloud into a global descriptor, a single feature vector that summarizes the entire point cloud geometry. Our model takes inspiration from Generative Image-to-text Transformer (GIT) [24] which is a Vision Transformer (ViT) used for image captioning. Fig. 1 illustrates the whole process: the GIT image encoder is replaced with a point cloud encoder where the text decoder is trained to map 3D data to unique identifiers. The main contributions of this paper are:

* We propose DSI-3D, an adaptation of DSI methods for scalable 3D point clouds retrieval, represented by state-of-the-art descriptors (e.g. LoGG3D-Net), by training the model to map those representations to a corresponding *scene docids*.

* We introduce novel indexing strategies to enhance document representation, incorporating geocoding and Hilbert curve-based methods.

* We evaluate the proposal for place recognition, in order to facilitate the comparison with the state of the art.

This paper is organized as follows: Section II revisits the state of the art on 3D point cloud retrieval and main concepts, applied to the problem of place recognition. Section III introduces our proposal while Sections IV and V present its evaluation, before concluding in Section VI.

## II. RELATED WORK AND MAIN CONCEPTS

In this section, we present a state of the art on 3D point clouds retrieval in Section II-A, followed by a closer look at the loss function used by the descriptor employed, LoGG3D-Net, in Section II-B. We present the concepts of Differentiable Search Index in II-C and how it can be adapted to 3D data with a Vision-language model in Section II-D.

### A. Retrieval in 3D point clouds

Most 3D point cloud retrieval methods are applied to place recognition, i.e., locating a query cloud by matching it to the most similar clouds in a geolocated reference dataset. The reference is divided into smaller samples indexed with multi-dimensional descriptors. The query's descriptor is then computed and compared against the reference, and the best matches yield the most likely locations of the query. The current state of the art emphasizes the cloud description part, while the *k*-NN retrieval typically relies on exhaustive and sequential comparisons in the reference [23], or, slightly better, on tree-based indexes like *k*-d trees [8], [10], [11], [21]. Brute-force *k*-NN scales linearly with the size of the database, leading to slower performance on large datasets, while *k*-d trees lower the computational cost but become inefficient in high-dimensional spaces, often involved in 3D point cloud retrieval. There are several families of descriptors; a first distinction can be made between local and global feature-based strategies.

**Local features-based.** Local features gather and describe local information, like density or local 3D convolution, about a specific region of the cloud, such as particular points or voxels. These techniques may suffer from accuracy loss due to viewpoint changes or the need for dense point clouds. Convolutional Neural Networks (CNNs) have demonstrated strong feature learning capabilities for 2D image data [1], but their application to point clouds is challenging due to their sparse and unordered nature. PointNet [15] achieves direct feature learning from raw point cloud, while PointNet++ [16] extends this approach by recursively applying [15] learning hierarchical features considering distance metric.

In contrast, global features-based approaches represent the entirety of the query with one entity, often a vector. Sometimes, this global representation tends to extract global information from the aggregation of local features. They have the advantage of being viewpoint-invariant and computationally less expensive for the retrieval, but as with images, potentially less discriminative than local descriptors.

**Global features handcrafted-based.** Handcrafted-based features do not rely on a previous model learning to be applied for point cloud description. Among them, we can cite Scan Context [10] which encodes a scene into one rotation-invariant global descriptor using a polar projection of visible points, without requiring prior training. However, this approach struggles with lateral offsets invariance. Scan Context++ [9] addresses this issue by employing polar and Cartesian context.

**Global learned features-based.** By contrast with hand-crafted methods, learned point cloud descriptors have benefited from deep learning. A pioneering end-to-end learning-based method, PointNetVLAD [21], generates a global descriptor from point cloud data. It combines PointNet [15] for local feature extraction, with NetVLAD [1], a learnable CNN layer that aggregates local features into a single global descriptor.

**Global features sparse convolution.** MinkLoc3D [11] enhances local feature extraction by introducing the first 3D sparse convolution-based architecture. A local feature extraction module is applied to the sparsified point clouds, and a global descriptor is produced using Generalized-Mean pooling [17]. Similarly, LoGG3D-Net [23] builds upon sparse volumetric methods, like those in MinkLoc3D, but introduces a local consistency loss function. This function enforces local feature similarity between a query and a positive point cloud (within $3m$), leading to more robust local descriptors. The global descriptor is then obtained using second-order pooling [22]. In Section II-B, we take a closer look at this approach, especially its quadruplet loss, which has inspired our work.

**Multi-sourced global features.** Cross-source 3D place recognition compares point clouds from different viewpoints, such as ground and aerial LiDAR, which differ in coverage, density, and noise. To address these gaps, CrossLoc3D [8] learns a shared embedding space between ground and aerial scans using multi-scale sparse convolutions, a NetVLAD aggregator, and iterative refinement.
A. DSI-3D

Exploiting the DSI method requires converting 3D data into text form. This involves a two-step process: first, encoding the 3D point cloud into an embedding, and then passing this embedding through a multimodal transformer to generate captions. For the point cloud encoding, we use LoGG3D-Net [23] due to its local consistency loss, which significantly enhances retrieval performances for place recognition, but other point cloud global descriptors could be used. The multimodal transformer chosen is GIT [24] for its streamlined architecture (see Section II-D). By substituting the image encoder of GIT with a 3D encoder, we adapt it to generate captions that serve as docids for point clouds, derived from scene descriptors. In order to reinforce the training by increasing the similarity between positive pairs as in LoGG3D-Net, we use both the regular GIT loss and a variation of the language modeling $L_m$ loss (3) to be triplet and quadruplet losses $L_{trip1}$ and $L_{quad}$ (both $\in [0, +\infty)$). These losses are computed using tuples of point clouds: $(P_q, P_p, P_n)$ for the triplet one, and $(P_q, P_p, P_n, P_{nbis})$ for the quadruplet one, as follows:

$$L_{trip1} = L_m + (L_{mpos} - L_{mneg} + \alpha) \quad (5)$$

$$L_{quad} = L_{trip1} + (L_{mpos} - L_{mnegbis} + \beta) \quad (6)$$

With $L_{mpos}$, $L_{mneg}$ and $L_{mnegbis}$ representing the cross-entropy loss between the docid of a query point cloud $P_q$ and output logits for a positive point cloud $P_p$, a negative point cloud $P_n$, and a second negative point cloud $P_{nbis}$, respectively. $P_{nbis}$ forms a negative pair with both the query $P_q$ and the first negative $P_n$; $\alpha$ and $\beta$ are resp. fixed at 0.5 and 0.3. Finally, the retrieval step is performed with a beam search with a restricted vocabulary to meaningful indexes.

B. Docid representation

For the representation of the docid, we exclude *Unstructured Atomic identifiers* (see Section II-C), as they are the least scalable option. For *Naively Structured String identifiers*, a natural analogy can be drawn with the naming of each point cloud in classical benchmarks with acquisition sequences (e.g. KITTI [7] for mobile mapping), where each point cloud is named sequentially from 0 to N. The *Semantically Structured identifiers* strategy is also assessed. In this approach, neighboring point clouds with similar descriptors, and thus being in the same cluster, will share similar identifier prefixes.

Additionally, we introduce *Positional Structured identifiers*, a novel representation tailored for place recognition where the coordinates of a point cloud are defined in a Cartesian coordinate system, denoted as $X_N=\{x_0, \dots, x_{N-1}\}$ and $Y_N=\{y_0, \dots, y_{N-1}\}$ (the $Z_N$ coordinate being excluded here as we focus on planar geolocation), corresponding to the set of strings values of the center coordinates of a sequence of point clouds of length N. We propose generating unique identifiers by interlacing the digit strings coordinates of each point cloud $n$, $x_n$ and $y_n$, starting from the most significant digit of $x_n$ down to centimeter precision of $y_n$. The values of

the coordinates $X_N$ and $Y_N$ are shifted to include only non-negative values and scaled to ensure centimeter-level accuracy, enabling unique identifiers even for closely revisited locations.

As an example, the docid returned for a point cloud $n$ with center coordinates $x_n=’1111’$ and $y_n=’2222’$ will be $docid=’12121212’$. This bijective mapping between point clouds and identifiers guarantees that each revisit of a scene will have a closely related identifier. We also propose a variant of this positional indexing, using space-filling curves, which map a multidimensional grid space onto a 1D curve, such as the Hilbert curve, known for its superior locality preservation [6]. After shifting and rescaling the $X_N$ and $Y_N$ center coordinates into positive integers, each point cloud center is assigned a unique identifier derived from the Hilbert curve. This identifier corresponds to the distance the curve must travel to reach point $(X_N, Y_N)$, ensuring that the spatially close points have similar index representations. Empirically, for our experiments with the KITTI dataset, we apply the Hilbert curve with 17 iterations, resulting in a grid resolution of $2^{17} \times 2^{17}$.

IV. EXPERIMENTAL SETUP

In this section, we present the dataset, the evaluation criteria, and the experimental setup chosen. We use LoGG3D-Net as a 3D encoder for DSI-3D due to its good performances in the state of the art, while other global descriptors could be used.

A. Dataset

To ensure comparability with the state of the art, we evaluated our approach for place recognition using the classical KITTI LiDAR datasets [7]. We trained and evaluated our model on the six sequences containing revisits (seq. 00, 02, 05, 06, 07, and 08) to assess the robustness of each variant of our method. These sequences represent a total of 18236 unique scenes, divided as follows according to the sequence: 4541, 4661, 2761, 1101, 1101 and 4071 point clouds, covering approximately 1.13km². To give insight on the scalability of our model, we constructed a new sequence, numbered 22, by concatenating point clouds from the original six ones. Since each sequence is defined in local coordinates, we applied a shift of ($i \times 1000m, i \times 1000m$,) to each point cloud coordinates, where $i$ represents the sequence number during the combination process, to prevent overlapping sequences. 80% of each sequence is allocated to the training set, while the remaining 20% is equally divided between the validation and evaluation sets. Point clouds are assigned to these sets based on their *Naively Structured String identifiers* as follows: those with indices not divisible by five are placed in the training set; those with indices divisible by ten are assigned to the evaluation set; and the remaining point clouds (indices divisible by five but not by ten) are included in the validation set. This division creates a gap every five point clouds, allowing the model to be evaluated on its ability to identify the closest neighbors of scenes it was not trained on. During evaluation, the point clouds in the training set are computed and stored into a 'seen
place' database to replicate the parametrization of the training set of our model.

## B. Evaluation Criteria and baseline

Two main criteria are used to evaluate DSI-3D and the baseline:

* The *Hits@N* metric, used in information retrieval, reports the proportion of correct docid ranked within the top-*N* predictions. Here, we focus on the more discriminative case with *N* = 1.

* From a place recognition perspective, we evaluate encoding performance based on the maximum *F*1 score or *F*1max for each sequence [22], [23]. For LoGG3D-Net [23], it is obtained by varying the similarity threshold that maximizes the *F*1 score. We adapt this *F*1 score threshold for our model, by iterating over logit score, while maintaining the same geometric revisit criteria as in [23]. A top-1 retrieval is considered positive if its logit score is below the maximum confidence threshold. A positive retrieval is classified as true positive if it is within 3m of the ground truth pose of the query, and as false positive if it exceeds 20m. For negative retrievals, where the logits exceed the maximum confidence threshold, a true negative is assigned if the query is not revisited, meaning no point cloud within 3m of the location of the query is observed with a timestamp greater than 30s; otherwise, it is considered as a false negative. With this criterion, a retrieved point cloud with a low logit score (high model confidence) but inaccurate geolocation is considered a false positive.

As baselines, we compare DSI-3D facing two other k-NN retrieval strategies:

* **Exact retrieval**, based on the exhaustive comparison of all the descriptors in the reference, as in the state of the art;

* More efficiently, **approximate retrieval**, based on approximate nearest neighbor (ANN) [14] relying on Locality Sensitive Hashing (LSH) and Hierarchical navigable small world (HNSW) from the FAISS library [4]. We used the binary flat LSH index, where the number of bits $H \in \{32, 256\}$ corresponds to the number of random hyperplane projections (or random rotations in this implementation), quantifying two degrees of approximation. For HNSW, the number of neighbor connections is set to $v = 32$.

All these retrieval strategies exploit LoGG3D-Net as point cloud descriptor.

## C. Implementation Details

The experiments are conducted using a PyTorch implementation on a single V100 GPU. For training the DSI model, we use the pre-trained 3D encoder from LoGG3D-Net and the text decoder from the base-sized GIT checkpoint, fine-tuned on COCO<fnref n="1" />. The evaluation is done using the public

implementation of LoGG3D-Net and the checkpoints exploited for each sequence were selected using the leave-one-out strategy. For the combined sequence 22, we employed the LoGG3D-Net checkpoint trained while leaving out sequence 00, ensuring that all 18236 scenes were encoded within the same representation space. The best GIT checkpoints are retained for evaluating each sequence and indexing strategy, based on their performance on the validation set. Positive and negative point cloud pairs are sampled based on distances set to *p* = 3 and *n* = 20m during the training. Setting *n* = 20m during the evaluation leads to undiscriminating results between the different approaches. A solution to distinguish the best model was to set *n* = 3m during the evaluation. This stricter threshold highlights the ability of the model to identify neighbors close to the query.

## V. RESULTS

This section is organized as follows: Section V-A evaluates the impact of the loss function on the training of DSI-3D in terms of retrieval performance. Then Section V-B evaluates DSI-3D facing different retrieval strategies. Finally, Section V-C discusses the scalability of our approach in terms of complexity and retrieval time.

### A. Loss function

Table I presents the *F*1max and *Hits@1* scores obtained for the six original sequences on our model, with the GPS strategy, by exploiting the triplet and the quadruplet losses of Section III-A (again with a negative distance threshold of 3m). We observe that the quadruplet loss achieves a marginally higher average *F*1max score and *Hits@1* score than the triplet loss, at equivalent training epochs. For the remaining experiments, we chose the quadruplet loss.

<table><caption>TABLE I
SCORES OBTAINED AT EQUIVALENT TRAINING STEPS FOR LOSS FUNCTION COMPARISON ON DSI-3D</caption><thead><tr><th></th><th>00</th><th>02</th><th>05</th><th>06</th><th>07</th><th>08</th><th>mean</th></tr></thead><tbody><tr><th>F1max</th><td>0.9775</td><td>0.9725</td><td>0.9946</td><td>0.9479</td><td>0.9817</td><td>0.9875</td><td>0.9770</td></tr><tr><th>L<sub>tripl</sub></th><td>0.9809</td><td>0.9713</td><td>0.9853</td><td>0.9674</td><td>0.9955</td><td>0.9825</td><td>0.9805</td></tr><tr><th>Hits@1</th><td>00</td><td>02</td><td>05</td><td>06</td><td>07</td><td>08</td><td>mean</td></tr><tr><th>L<sub>tripl</sub></th><td>0.9560</td><td>0.9465</td><td>0.9892</td><td>0.9009</td><td>0.9640</td><td>0.9755</td><td>0.9554</td></tr><tr><th>L<sub>quad</sub></th><td>0.9626</td><td>0.9422</td><td>0.9711</td><td>0.9369</td><td>0.9909</td><td>0.9704</td><td>0.9624</td></tr></tbody></table>

### B. Indexing strategies comparison

Table II and Table III report the *F*1max and *Hits@1* scores for the baselines and DSI-3D variants. 'Exact k-NN' denotes exhaustive exact retrieval, LSH<sub>H</sub> refers to approximate retrieval with $H \in \{32, 256\}$, and HNSW<sub>v</sub> corresponds to HNSW with $v = 32$. The names 'Label', 'Hierar', 'GPS' and 'Hilbert' refer to the DSI-3D indexing strategies *Naively Structured String identifiers*, *Semantically Structured identifiers*, *Positional Structured identifiers* and *Hilbert curve Positional Structured identifiers* respectively. Sequence 22 was only trained with the *Hilbert curve Positional Structured identifiers* as it is the most promising indexing strategy.

<footnote n="1">¹https://huggingface.co/microsoft/git-base-coco</footnote>
<caption>TABLE II</caption>

EVALUATION ACROSS MULTIPLE KITTI SEQUENCES USING VARIOUS INDEXING STRATEGIES, BASED ON LOGG3D-NET DESCRIPTORS, USING THE $F1_{max}$ METRIC. TWO BEST RESULTS IN BOLD AND UNDERLINED.

<table><caption>TABLE III</caption><thead><tr><th>Indexing</th><th>00</th><th>02</th><th>05</th><th>06</th><th>07</th><th>08</th><th>22</th></tr></thead><tbody><tr><td>Exact k-NN</td><td><strong>0.9956</strong></td><td><strong>0.9859</strong></td><td><strong>1.0</strong></td><td><strong>0.9954</strong></td><td><strong>1.0</strong></td><td><strong>0.9974</strong></td><td><strong>0.9925</strong></td></tr><tr><td>LSH<sub>256</sub></td><td>0.9945</td><td>0.9792</td><td>0.9946</td><td>0.9815</td><td>0.9626</td><td>0.9888</td><td>0.9850</td></tr><tr><td>LSH<sub>32</sub></td><td>0.9416</td><td>0.8979</td><td>0.9681</td><td>0.9051</td><td>0.9670</td><td>0.9448</td><td>0.9290</td></tr><tr><td>HNSW<sub>32</sub></td><td><strong>0.9956</strong></td><td><strong>0.9859</strong></td><td><strong>1.0</strong></td><td><strong>0.9954</strong></td><td><strong>1.0</strong></td><td><strong>0.9974</strong></td><td><strong>0.9925</strong></td></tr><tr><td>DSI-3D with Label</td><td>0.8991</td><td>0.8774</td><td>0.7906</td><td>0.7954</td><td>0.8844</td><td>0.9044</td><td>/</td></tr><tr><td>DSI-3D with Hierar</td><td>0.9635</td><td>0.9316</td><td>0.9684</td><td>0.9626</td><td>0.9817</td><td>0.9684</td><td>/</td></tr><tr><td>DSI-3D with GPS</td><td>0.9809</td><td>0.9758</td><td>0.9891</td><td>0.9674</td><td>0.9955</td><td>0.9851</td><td>/</td></tr><tr><td>DSI-3D with Hilbert</td><td>0.9933</td><td>0.9781</td><td>0.9909</td><td>0.9817</td><td>0.9955</td><td>0.9913</td><td>0.9819</td></tr></tbody></table>

EVALUATION ACROSS MULTIPLE KITTI SEQUENCES USING VARIOUS INDEXING STRATEGIES, BASED ON LOGG3D-NET DESCRIPTORS, USING THE *Hits@1* METRIC. TWO BEST RESULTS IN BOLD AND UNDERLINED.

<table><thead><tr><th>Indexing</th><th>00</th><th>02</th><th>05</th><th>06</th><th>07</th><th>08</th><th>22</th></tr></thead><tbody><tr><td>Exact k-NN</td><td><strong>0.9956</strong></td><td><strong>0.9722</strong></td><td><strong>1.0</strong></td><td><strong>0.9910</strong></td><td><strong>1.0</strong></td><td><strong>0.9950</strong></td><td><strong>0.9852</strong></td></tr><tr><td>LSH<sub>256</sub></td><td>0.9890</td><td>0.9572</td><td>0.9892</td><td>0.9550</td><td>0.9820</td><td>0.9755</td><td>0.9693</td></tr><tr><td>LSH<sub>32</sub></td><td>0.6110</td><td>0.5225</td><td>0.6173</td><td>0.5676</td><td>0.8108</td><td>0.6176</td><td>0.5049</td></tr><tr><td>HNSW<sub>32</sub></td><td><strong>0.9912</strong></td><td><strong>0.9722</strong></td><td><strong>1.0</strong></td><td><strong>0.9910</strong></td><td><strong>1.0</strong></td><td><strong>0.9950</strong></td><td><strong>0.9852</strong></td></tr><tr><td>DSI-3D with Label</td><td>0.8132</td><td>0.7645</td><td>0.8831</td><td>0.6306</td><td>0.7928</td><td>0.8235</td><td>/</td></tr><tr><td>DSI-3D with Hierar</td><td>0.9319</td><td>0.8630</td><td>0.9387</td><td>0.9279</td><td>0.9640</td><td>0.9387</td><td>/</td></tr><tr><td>DSI-3D with GPS</td><td>0.9626</td><td>0.9507</td><td>0.9783</td><td>0.9369</td><td>0.9909</td><td>0.9705</td><td>/</td></tr><tr><td>DSI-3D with Hilbert</td><td>0.9846</td><td>0.9550</td><td>0.9819</td><td>0.9640</td><td>0.9910</td><td>0.9828</td><td>0.9644</td></tr></tbody></table>

Across both evaluation metrics (Tables II and III), LSH-based acceleration degrades LOGG3D-Net retrieval quality to varying degrees depending on *H*, whereas HNSW achieves scores comparable to the exact search. Secondly, among the indexing strategies tested for DSI-3D, Hilbert curve indexing performs best, suggesting that state-of-the-art methods like 'Label' and 'Hierar' may be outdated for place recognition retrieval. This version does not achieve the same performance as the exact baseline, which provides a slightly better *Hits@1* score, by an average improvement of 1.6% (median at 1.3%) ; for $F1_{max}$, 'Hilbert' is less efficient of 0.8% on average (median at 0.5%). However, we observe the same behavior, as well as scores comparable to DSI-3D ones, for approximate retrieval when adding LSH<sub>256</sub> to LOGG3D-Net. Globally, DSI-3D with Hilbert curve indexing achieves even a higher average $F1_{max}$ than LOGG3D-Net with LSH<sub>256</sub> by 0.4% (median at 0.6%) and a better average *Hits@1* by 0.1% (median at 0.6%).

In conclusion of this section, the behavior of DSI-3D, in terms of retrieval quality, can be considered similar as a classic state-of-the-art approximate approach. In the following section, we discuss its superiority facing the questions of complexity and retrieval time.

### C. Complexity and retrieval time

In its current implementation [23], retrieval with LOGG3D-Net is performed over the entire reference dataset by sequential comparisons (first line of Tables II and III). This makes the retrieval time proportional to the size of the dataset ($n$) with a time complexity $O(n)$. The similarity search in such high-dimensional spaces can be accelerated with indexes such as the LSH or HNSW, as experimented in the same Tables (lines 2 and 3). The LSH complexity differs from the variant used

but is generally dominated by $O(n^p)$ with $0 \le p \le 1$, under the approximate retrieval assumption. HNSW is associated with a $O(\log n)$ complexity, whereas DSI-3D relies on model inference with constant $O(1)$ complexity, offering a significant advantage for large point cloud datasets. It also works under the approximate retrieval paradigm. However, as we have experimented in the previous section, the retrieval quality remains fully comparable to those of the other solutions.

In terms of retrieval time of a Top-10, exact retrieval with LOGG3D-Net, in its public implementation, ranges from 0.0007 to 0.0109s in average for all the queries. With LSH<sub>256</sub>, it is 6.72 times faster, 8.10 times faster with LSH<sub>32</sub> (but with a poor retrieval quality) and 5.67 times faster with HNSW. For DSI-3D indexed with *Positional Structured identifiers*, currently retrieval time is 0.095s, by measuring the time it takes for a descriptor to pass through all GIT layers and return the docid. It is worth noting that the current code implementation used for the article is not yet optimized. Nevertheless, to give an insight on the current scalability of DSI-3D, we fitted a linear equation between the size of the reference datasets ($N_{desc}$) and retrieval times ($T$) with exact retrieval ($T = 0.75N_{desc} - 0.03$). This allows us to estimate that the inversion point occurs at $N_{desc} = 126.7e3$ descriptors in favor of DSI-3D. According to the settings used, this amount roughly corresponds to a spatial coverage of 8.15km², at which point DSI-3D would become faster in its current yet not optimized implementation. Among the factors also affecting the retrieval time of DSI-3D is the number of beams explored during the beam search, which is fixed at 10, as well as the indexing strategies, affecting decoding steps. Reducing the number of beams could improve retrieval time but may result in less precise responses. Such an evaluation will be part of future experiments.

## VI. CONCLUSION

In this article, we have presented DSI-3D, a new indexing and retrieval strategy for 3D point clouds. With a constant complexity, it drastically accelerates retrieval with global point cloud descriptors, compared to current literature which mainly focuses on point cloud description and performs retrieval following a linear time complexity (which can be slightly improved with off-the-shelf index such as LSH and HSNW). The proposal adapts the Differentiable Search Index and introduces two new *Positional Structured Identifiers* tailored for place recognition. This article has laid the foundations of the approach, exhibiting performances similar to those of the state of the art in terms of retrieval quality.

Beyond implementation optimizations, future work will explore applying DSI-3D to very large datasets, such as aerial LiDAR campaigns covering entire regions, for example, 1.5M point cloud scenes spanning the 105 km² Paris area. To support this scalability, Mixture of Experts (MoE) [2] architectures offer a promising direction: each expert, a dedicated DSI-3D model, can specialize in a specific geographic region. MoEs enable parallelizable retrieval, and are easier to train and to update compared to a single, monolithic model.
REFERENCES

[1] Relja Arandjelovic, Petr Gronat, Akihiko Torii, Tomas Pajdla, and Josef Sivic. Netvlad: Cnn architecture for weakly supervised place recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 5297–5307, 2016.

[2] Weilin Cai, Juyong Jiang, Fan Wang, Jing Tang, Sunhun Kim, and Jiayi Huang. A survey on mixture of experts. arXiv preprint arXiv:2407.06204, 2024.

[3] Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. Autoregressive entity retrieval. arXiv preprint arXiv:2010.00904, 2020.

[4] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint arXiv:2401.08281, 2024.

[5] Shiv Ram Dubey. A decade survey of content based image retrieval using deep learning. *IEEE Transactions on Circuits and Systems for Video Technology*, 32(5):2687–2704, 2021.

[6] Christos Faloutsos and Shari Roseman. Fractals for secondary key retrieval. In *Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems*, pages 247–252, 1989.

[7] Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun. Vision meets robotics: The kitti dataset. *The international journal of robotics research*, 32(11):1231–1237, 2013.

[8] Tianrui Guan, Aswath Muthuselvam, Montana Hoover, Xijun Wang, Jing Liang, Adarsh Jagan Sathyamoorthy, Damon Conover, and Dinesh Manocha. Crossloc3d: Aerial-ground cross-source 3d place recognition. In *Proceedings of the IEEE/CVF International Conference on Computer Vision*, pages 11335–11344, 2023.

[9] Giseop Kim, Sunwook Choi, and Ayoung Kim. Scan context++: Structural place recognition robust to rotation and lateral variations in urban environments. *IEEE Transactions on Robotics*, 38(3):1856–1874, 2021.

[10] Giseop Kim and Ayoung Kim. Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map. In *2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*, pages 4802–4809. IEEE, 2018.

[11] Jacek Komorowski. Minkloc3d: Point cloud based large-scale place recognition. In *Proceedings of the IEEE/CVF winter conference on applications of computer vision*, pages 1790–1799, 2021.

[12] Stephanie Lowry, Niko Sünderhauf, Paul Newman, John J Leonard, David Cox, Peter Corke, and Michael J Milford. Visual place recognition: A survey. *ieee transactions on robotics*, 32(1):1–19, 2015.

[13] Rodrigo Nogueira, Jimmy Lin, and AI Epistemic. From doc2query to docttttquery. *Online preprint*, 6(2), 2019.

[14] J.J. Pan, J. Wang, and G Li. Survey of vector database management systems. *The International Journal on Very Large Data Bases*, 33, 2024.

[15] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 652–660, 2017.

[16] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. *Advances in neural information processing systems*, 30, 2017.

[17] Filip Radenović, Giorgos Tolias, and Ondřej Chum. Fine-tuning cnn image retrieval with no human annotation. *IEEE transactions on pattern analysis and machine intelligence*, 41(7):1655–1668, 2018.

[18] Ihsan Sabuncuoğlu and M Bayiz. Job shop scheduling with beam search. *European Journal of Operational Research*, 118(2):390–412, 1999.

[19] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. *Advances in neural information processing systems*, 27, 2014.

[20] Yi Tay, Vinh Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Gupta, et al. Transformer memory as a differentiable search index. *Advances in Neural Information Processing Systems*, 35:21831–21843, 2022.

[21] Mikaela Angelina Uy and Gim Hee Lee. Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 4470–4479, 2018.

[22] Kavisha Vidanapathirana, Peyman Moghadam, Ben Harwood, Muming Zhao, Sridha Sridharan, and Clinton Fookes. Locus: Lidar-based place recognition using spatiotemporal higher-order pooling. In *2021 IEEE International Conference on Robotics and Automation (ICRA)*, pages 5075–5081. IEEE, 2021.

[23] Kavisha Vidanapathirana, Milad Ramezani, Peyman Moghadam, Sridha Sridharan, and Clinton Fookes. Logg3d-net: Locally guided global descriptor learning for 3d place recognition. In *2022 International Conference on Robotics and Automation (ICRA)*, pages 2215–2221. IEEE, 2022.

[24] Jianfeng Wang, Zhengyuan Yang, Xiaowei Hu, Linjie Li, Kevin Lin, Zhe Gan, Zicheng Liu, Ce Liu, and Lijuan Wang. Git: A generative image-to-text transformer for vision and language. arXiv preprint arXiv:2205.14100, 2022.

[25] Yongjun Zhang, Pengcheng Shi, and Jiayuan Li. Lidar-based place recognition for autonomous driving: A survey. *ACM Computing Surveys*, 57(4):1–36, 2024.

[26] Shengyao Zhuang, Houxing Ren, Linjun Shou, Jian Pei, Ming Gong, Guido Zuccon, and Daxin Jiang. Bridging the gap between indexing and retrieval for differentiable search index with query generation. arXiv preprint arXiv:2206.10128, 2022.