# Fast 3D point clouds retrieval for Large-scale 3D Place Recognition

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

► To cite this version:

Chahine-Nicolas Zede, Laurent Caraffa, Valérie Gouet-Brunet. Fast 3D point clouds retrieval for Large-scale 3D Place Recognition. ORASIS, journées francophones des jeunes chercheurs en vision par ordinateur, Jun 2025, Le Croisic, France. 10.48550/arXiv.2502.21067. [hal-05046766]

HAL Id: hal-05046766

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

Submitted on 25 Apr 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
Fast 3D point clouds retrieval for Large-scale 3D Place Recognition

Chahine-Nicolas Zede

Laurent Caraffa

Valérie Gouet-Brunet

LASTIG, IGN-ENSG, Gustave Eiffel University, 77420 Champs-sur-Marne, France

chahine-nicolas.zede@ign.fr, laurent.caraffa@ign.fr, valerie.gouet@ign.fr

## Résumé

Rechercher un nuage de points 3D est une tâche difficile qui consiste à identifier, au sein d'une base de référence, les nuages les plus similaires à un nuage requête donné. Les méthodes actuelles se concentrent principalement sur la description de ces nuages de points comme indicateur de similarité. Dans ce travail, nous nous focalisons sur l'accélération de la recherche en adaptant le *Differentiable Search Index* (DSI), basé sur les transformers et initialement conçu pour la recherche d'information textuelle, à la recherche dans les nuages de points. Notre approche génère des identifiants 1D, associés à des descripteurs 3D, permettant ainsi une recherche très efficace en temps constant. Pour adapter cette approche aux nuages de points, nous utilisons les *Vision Transformers* qui associent les descripteurs multidimensionnels à leurs identifiants 1D, tout en intégrant un encodage positionnel et sémantique. Les performances de notre proposition sont évaluées face à l'état de l'art sur un jeu de données public, dans le contexte de la reconnaissance de lieux, en termes de qualité et rapidité des réponses retournées.

## Mots Clef

Recherche 3D, recherche à grande échelle, descripteurs 3D, index de recherche différentiable, Reconnaissance de lieux basée sur le LiDAR.

## 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. 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 clouds 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.

## Keywords

3D retrieval, Scalable retrieval, 3D point cloud descriptors, Differentiable Search Index (DSI), LiDAR-based place recognition

# 1 Introduction

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

Retrieval in 3D point clouds involves finding the most similar point clouds to a given query within a reference database of 3D point clouds. Research on retrieval within 3D point clouds is still in its early stages. Existing solutions mainly focus on the indexing phase (i.e. the production of point cloud descriptors) rather than the retrieval phase, which involves efficiently finding similar descriptors in the reference. The current state of the art confirms that the main application of retrieval in point clouds is geolocalization. Unlike approaches relying on visual place recognition, 3D LiDAR point clouds have the benefits of being invariant to lighting and weather conditions [13], making them particularly relevant for this purpose.

**Applications of retrieval in point clouds.** Improving geolocation accuracy of a system, based on LiDAR acquisitions, has several 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
<figure><img src="image_2.png" /><figcaption>Figure 1: Differentiable search index pipeline [21] adapted for 3D data retrieval using GIT architecture [25]. (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>

reducing drift in Simultaneous Localization and Mapping (SLAM) systems [26]. This could extend to media verification, fact checking videos for example, by geolocating 3D point clouds reconstructed from video (e.g with Structure-From-Motion).

The main objective of the article is to contribute to the
retrieval phase, by proposing a scalable retrieval method,
facing the size of the reference dataset and the dimen-
sionality of the descriptors. We explore the application
of Differentiable Search Index (DSI) [21] methods, origi-
nally developed for Information Retrieval in large text cor-
pora, to the domain of 3D point clouds. DSI employs a
single T5 (text-to-text transfer transformer) model to map
string queries to relevant document identifiers (docids). To
bridge the gap between the 3D point cloud queries and
the textual input required for Information Retrieval, we ex-
plored existing Place Recognition methods, such as Point-
NetVLAD [22] and LoGG3D-Net [24]. These methods
have shown promising results in loop detection by encod-
ing a point cloud into a global descriptor, a single fea-
ture vector that summarizes the entire point cloud geom-
etry. Our model takes inspiration from Generative Image-
to-text Transformer (GIT) [25] which is a Vision Trans-
former (ViT) used for image captioning. Fig. 1 illustrates
the whole process, where the GIT image encoder is re-
placed 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 to support scalable retrieval in 3D point clouds by training the model to map a point cloud representation to a corresponding *scene docid*.
* We introduce novel indexing strategies to enhance document representation, incorporating geocoding

and Hilbert curve-based methods.

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

## 2 Related work and main concepts

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

## 2.1 Retrieval in 3D point clouds

Most of the approaches of retrieval in 3D point clouds en-
countered are applied to the problem of place recognition.
This involves determining the geolocation of a points cloud
query from the most similar clouds retrieved in a geolocal-
ized reference. First, the reference dataset is usually di-
vided into multiple smaller samples, each of them being
geolocalized and indexed with a descriptor. Second, the
same type of descriptor is computed for the query and com-
pared to those of the reference dataset. The best matches
yield the most likely locations of the query.
There are multiple families of representation for 3D point
clouds. A first distinction can be made between local and
global feature-based strategies.

**Local features-based.** Local features gather local information, like density or local 3D convolution, about a specific region of the cloud, such as particular points or voxels. These place recognition 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 LiDAR-based Place Recognition is challenging due to the sparse and unordered nature of point clouds. PointNet [16] achieves direct features learning from raw point cloud, while PointNet++ [17], extends this approach by recursively applying [16], learning hierarchical features considering distance metric.

In contrast, there is also a global features-based approach
that represents the entirety of the query with one object,
often a vector. 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.

**Global features handcrafted-based.** Handcrafted-based features do not rely on a previous model learning to be applied for place recognition. Among them, we can cite Scan Context [9] 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++ [8] addresses this issue by employing polar and Cartesian context.

**Global learned features-based.** By contrast with hand-crafted methods, learned point clouds descriptors have benefited from deep learning. A pioneering end-to-end learning-based method, PointNetVLAD [22], generates a global descriptor from point cloud data. It combines Point-Net [16] for local feature extraction, with NetVLAD [1], a learnable CNN layer that aggregates local features into a single global descriptor. Since NetVLAD is a symmetric function, i.e, it is input order invariant, so can be applied to unordered point clouds.

**Global features graph-based.** To better capture structural information in large-scale environments, graph-based methods model the relationship between an object and its topology. LPD-Net [12] introduces graph-based aggregation to analyze spatial distribution. It computes ten types of local features, including curvature changes, local point density, and 2D scattering, for each point. A Graph Neural Network (GNN) is then used to aggregate points distributions and local features into a feature space and a Cartesian space respectively. Finally, NetVLAD [1] generates the global descriptor. While LPD-Net improves retrieval performances upon previous results, it may be limited by its high computational cost and architectural complexity.

**Global features segment-based.** Segment-based methods divide a scene into meaningful regions (e.g., roads, buildings, vegetation), providing a more structured representation that captures topological relationships between segments, rather than treating the entire point cloud as a single entity. Locus [23] aggregates these segment-based representations into a global descriptor, by modeling the topological relationships and temporal consistency segment feature. This is achieved via second-order pooling, where local features are represented as a matrix, by using the outer product with its transposed matrix and taking the element-wise maximum. It is followed by Eigen-value Power Normalization (ePN) [11] is applied to enhance descriptor description.

**Global features sparse convolution.** MinkLoc3D [10] enhances local features 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 [18]. Similarly, LoGG3D-Net [24] 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 [23]. In Section 2.2, 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 concerns the confrontation of point clouds acquired at different viewpoints, e.g. ground-based LiDAR

scans with aerial ones. It presents significant challenges due to differences in coverage, density and noise patterns. To bridge the representation gaps of those types of acquisition, CrossLoc3D [7] introduces a cross-source 3D matching approach. It learns a shared embedding space between aerial LiDAR database and ground LiDAR scans. It employs multi-scale sparse convolutions for feature selection, followed by a NetVLAD aggregator to obtain a unique descriptor. An iterative refinement step aligns the two embedding spaces into a shared one.

## 2.2 LoGG3D-Net

To reinforce the global descriptors similarity during the training, approach LoGG3D-Net applies a quadruplet loss $L_{quad} \in [0, +\infty[$, to a tuple $(P_q, P_p, P_n, P_{nbis})$:

$$L_{quad} = \sum_{i}^{N} ( [ \|g(P_q) - g(P_p)\|_2^2 - \|g(P_q) - g(P_n i)\|_2^2 + \alpha ]_+ + [ \|g(P_q) - g(P_p)\|_2^2 - \|g(P_{nbis}) - g(P_n i)\|_2^2 + \beta ]_+) \quad (1)$$

where $P_q$ is the query point cloud, $P_p$ is a positive one within $p = 3m$ of the query, $P_n$ is a negative point cloud distant from $n = 20m$ of the query, $P_{nbis}$ respects the negative condition with both $P_p$ and $P_n$. $g(P_*)$ is the final global descriptor vector. $N$ is the number of sampled negatives and $\|\cdot\|_+$ the hinge loss function, while $\alpha$ and $\beta$ are the loss margin of the quadruplet. For the retrieval step, the Cosine distance performs global descriptors retrieval by similarity between the query and the reference dataset items. In [24], previous entries adjacent to the query in time by less than 30s are excluded from the search to avoid matching with the same instance.

## 2.3 Differentiable Search Index

In text information retrieval, the objective is to find the most relevant document to answer a given question. Paper [21] introduces the Differentiable Search Index (DSI), a method that fully parameterized the traditionally multi-stage retrieve-then-rank pipeline within a single T5 transformer model. The DSI architecture also supports beam search, allowing it to return multiple possible answers ranked by their sequence scores. These scores, or logits $\in ]-\infty, +\infty[$ represent the raw prediction scores from the language modeling head for each token in the vocabulary before the SoftMax function. The SoftMax function converts them into probabilities over the classes such as Soft-Max(logits) $\in [0, 1]$. The probability score returned by the T5 model of the generated docid $i$ for a query $q$ can be computed as [27]:

$$p(i|q, \theta) = \prod_{i=1} p(i_t|T5_{\theta}(q, i_0, i_1, \dots, i_{t-1})) \quad (2)$$

where $i_t$ is the $i$-th token in the docid string. To achieve this, DSI operates in two fundamental modes:

**Indexing:** The DSI model learns to associate each document with its corresponding document identifier (docid)
using a sequence-to-sequence approach [20]. It takes the document tokens as input and generates the corresponding identifier as output.

**Retrieval:** For a given input query, the DSI model generates a ranked list of candidate docids through autoregressive generation [2]. More precisely, three strategies are used for representing docids in document retrieval:

**Unstructured Atomic Identifiers** is the simplest approach, where each document is represented by a unique, arbitrary integer identifier. The model is trained to emit one logit which is the last layer unscaled score of the model, for each unique docid, with the SoftMax function applied to the final layer's hidden state in the decoder. To retrieve the top-k documents, the logits are sorted, and the indices of the highest values are returned.

**Naively Structured String Identifiers** represents each document using arbitrary unique integers as tokenized strings, which avoids the need for a large SoftMax layer and simplifies training. A partial beam search tree [19] is employed to generate the top-k scores. It is similar to a multi-label classification.

**Semantically Structured Identifiers** encode semantic information within each document's identifier, structuring them to reduce the search space with each decoding step. This results in identifiers where semantically similar documents share common prefixes, facilitating retrieval. One method to construct these identifiers is to group similar descriptors by applying k-means clustering, then concatenating the resulting cluster indices to form each identifier.

A limitation of [21] is the size difference between the indexing phase, which processes an entire text document and the retrieval queries, which are sentence-sized. To address this, [27] proposes representing each document as a set of relevant queries, using the query generation model TQuery [14], leading to improved retrieval performances compared to the original DSI model. In our study, the retrieval and the indexing phase are both done on the same format of point clouds descriptors. However query generation could be a way to reinforce the mapping between a scene and its index.

## 2.4 Feature-to-text

To bridge the modality gap between text information and 3D points, we first explored existing Vision-Language (VL) models, which are trained on vision-language tasks such as generating image captions. Among image-to-text transformers, GIT stands out for its simple architecture [25], consisting of a single image encoder and a text decoder. The generated captions are decoded from the sequence of tokens with the highest scores. Decoding starts with a [BOS] (Beginning-Of-Sequence) token and proceeds in an autoregressive manner until reaching the [EOS] (End-Of-Sequence) token or the maximum sequence length.

During pre-training, for each image-text pair, the language modeling $L_m$ loss $\in [0, +\infty[$ is applied, with $I$ the image,

$y_i$ for $i \in \{1, \dots, N\}$ the text tokens, $y_0$ the [BOS] token and $y_{N+1}$ the [EOS] one:

$$L_m = \frac{1}{N+1} \sum_{i}^{N+1} (CE(y_i, P(y_j|J=0, \dots, i-1))) \quad (3)$$

where CE is the cross-entropy loss:

$$CE = - \sum_{c=1}^{C} \omega_c \mathrm{Log} \frac{\exp(x_c)}{\sum_{i=1}^{C} \exp(x_i)} \cdot y_c \quad (4)$$

and $x$ is the input logit, $y$ the target, $\omega$ the weight, and $C$ the number of classes.

# 3 Proposed Method

Inspired by the concepts of Section 2 and particularly the DSI search method [21], this work aims to bring the scalable aspect of text information retrieval to 3D point clouds retrieval.

## 3.1 DSI-3D

Applying 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 choose LoGG3D-Net [24] 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 [25] for its streamlined architecture (see Section 2.4). 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_{tripl}$ 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_{tripl} = L_m + (L_{mpos} - L_{mneg} + \alpha) \quad (5)$$

$$L_{quad} = L_{tripl} + (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.
## 3.2 Docid representation

For the representation of the docid, we exclude *Unstructured Atomic identifiers* (see Section 2.3), 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 for mobile mapping), where each point cloud is named sequentially from 0 to *N*. The *Se mantically Structured identifiers* strategy is also assessed. In this approach, neighboring point clouds with similar de scriptors, and thus being in the same cluster, will share sim ilar identifier prefixes. Naturally, this method extends well to revisits.

Additionally, we introduce *Positional Structured iden tifiers*, a novel representation tailored for place recog nition where the coordinates of a point cloud are de fined in a Cartesian coordinate system, denoted as $X_N=\{x_0, ..., x_{N-1}\}$ and $Y_N=\{y_0, ..., y_{N-1}\}$ (the $Z_N$ coordinate being excluded here as we focus on planar ge olocation), 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 [5]. 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}$.

# 4 Experimental Setup

In this section, we present the dataset, the evaluation crite-
ria and the experimental setup chosen. Here, LoGG3D-Net
serves both as our 3D encoder for DSI-3D and as a baseline
for comparison.

4.1 Dataset

To ensure comparability with the state of the art, we evalu-
ated our approach for place recognition using the classical
KITTI LiDAR datasets [6]. 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 verify the
scalability of our model, we constructed a new sequence,
numbered 22, by concatenating point clouds from the orig-
inal six ones. Since each sequence is defined in local co-
ordinates, we applied a shift of (i × 1000m, i × 1000m,) to each point cloud coordinates, where i represents the se-
quence 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 di-
vided 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 evalua-
tion 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, allow-
ing the model to be evaluated on its ability to identify the
closest neighbors of scenes it was not trained on. During
LoGG3D-Net 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.

## 4.2 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 F1 score or F1_max for each sequence [23, 24]. For LoGG3D-Net, it is found by iterating over the similarity threshold that maximizes the F1 score. We adapt this F1 score threshold for our model, by iterating over logit score, while maintaining the same geometric revisit criteria as in [24]. A top-1 retrieval is considered positive if its logits scores 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.

As baseline, we compare DSI-3D facing descriptor
LoGG3D-Net exploited within two retrieval strategies: first classically for exact retrieval based on the exhaustive comparison of all the descriptors in the reference and secondly, more optimally for approximate retrieval based on approximate nearest neighbor (ANN) [15] relying on Locality Sensitive Hashing (LSH) from the FAISS library [3]. More precisely, 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), respectively, named LSH$_{32}$ and LSH$_{256}$ in the experiments.

## 4.3 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.

# 5 Results

This experimental section is organized as follows: Section 5.1 evaluates the impact of the loss function on the training of DSI-3D in terms of retrieval performance. Then Section 5.2 evaluates our models, using different indexing strategies, and compares them to exact and approximate search methods. Finally, Section 5.3 discusses the scalability of our approach in terms of query complexity and retrieval time.

## 5.1 Loss function

Table 1 presents the $F1_{max}$ 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 3.1 (again with a negative distance threshold of $3m$). We observe that the triplet loss achieves a marginally higher average $F1_{max}$ score, while the quadruplet one performs slightly better on the *Hits@1* score. For the remaining experiments, we chose the quadruplet loss, as it provides the best results on both metrics for the longest sequences 00 and 02.

<table><caption>Table 1: Scores 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></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>L<sub>trip</sub></th><td>0.9775</td><td>0.9725</td><td><strong>0.9946</strong></td><td><strong>0.9674</strong></td><td>0.9954</td><td><strong>0.9875</strong></td><td><strong>0.9825</strong></td></tr><tr><th>L<sub>quad</sub></th><td><strong>0.9809</strong></td><td><strong>0.9758</strong></td><td>0.9891</td><td><strong>0.9674</strong></td><td><strong>0.9955</strong></td><td>0.9851</td><td>0.9823</td></tr><tr><th>Hits@1</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>L<sub>trip</sub></th><td>0.9560</td><td>0.9465</td><td><strong>0.9892</strong></td><td><strong>0.9369</strong></td><td>0.9820</td><td><strong>0.9755</strong></td><td><strong>0.9644</strong></td></tr><tr><th>L<sub>quad</sub></th><td><strong>0.9626</strong></td><td><strong>0.9507</strong></td><td>0.9783</td><td><strong>0.9369</strong></td><td><strong>0.9909</strong></td><td>0.9705</td><td><strong>0.9650</strong></td></tr></tbody></table>

## 5.2 Indexing strategies comparison

Table 2 and Table 3 resp. present the $F1_{max}$ scores and the *Hits@1* scores obtained for the LoGG3D-Net baseline (without and with index LSH) and several variants of DSI-3D. The names 'Label', 'Hierar', 'GPS' and 'Hilbert' refer to the 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.

Regardless of the evaluation criteria (Tables 2 and 3), we first observe that accelerating LoGG3D-Net retrieval with LSH affects the quality of the responses more or less, compared to exact retrieval (first line in each Table), depending on the value chosen for $H$.

Secondly, among the various indexing strategies tested for DSI-3D, Hilbert curve indexing yields the best results. This leads to the conclusion that the strategies of the state of the art ('Label' and 'Hierar') can be outdated for retrieval dedicated to place recognition. This version does not achieve the same performance as the exact baseline LoGG3D-Net, 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

<table><caption>Table 2: $F1_{max}$ scores for LoGG3D-Net (with and without LSH) and various strategies of DSI-3D.</caption><thead><tr><th>Model</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><th>LoGG3D-Net</th><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><th>LoGG3D-Net + LSH<sub>256</sub></th><td><strong>0.9945</strong></td><td><strong>0.9792</strong></td><td><strong>0.9946</strong></td><td>0.9815</td><td>0.9626</td><td>0.9888</td><td><strong>0.9850</strong></td></tr><tr><th>LoGG3D-Net + LSH<sub>32</sub></th><td>0.9416</td><td>0.8979</td><td><strong>0.9946</strong></td><td>0.9681</td><td>0.9670</td><td>0.9448</td><td>0.9290</td></tr><tr><th>Ours (Label)</th><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><th>Ours (Hierar)</th><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><th>Ours (GPS)</th><td>0.9809</td><td>0.9758</td><td>0.9891</td><td>0.9674</td><td><strong>0.9955</strong></td><td>0.9851</td><td>/</td></tr><tr><th>Ours (Hilbert)</th><td>0.9933</td><td>0.9781</td><td>0.9909</td><td><strong>0.9817</strong></td><td><strong>0.9955</strong></td><td><strong>0.9913</strong></td><td>0.9819</td></tr></tbody></table>

<table><caption>Table 3: *Hits@1* scores for LoGG3D-Net (with and without LSH) and DSI-3D.</caption><thead><tr><th>Model</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><th>LoGG3D-Net</th><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><th>LoGG3D-Net + LSH<sub>256</sub></th><td><strong>0.9890</strong></td><td><strong>0.9572</strong></td><td><strong>0.9892</strong></td><td>0.9550</td><td>0.9820</td><td>0.9755</td><td><strong>0.9693</strong></td></tr><tr><th>LoGG3D-Net + LSH<sub>32</sub></th><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><th>Ours (Label)</th><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><th>Ours (Hierar)</th><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><th>Ours (GPS)</th><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><th>Ours (Hilbert)</th><td>0.9846</td><td>0.9550</td><td>0.9819</td><td><strong>0.9640</strong></td><td><strong>0.9910</strong></td><td><strong>0.9828</strong></td><td>0.9644</td></tr></tbody></table>

<footnote n="1">¹https://huggingface.co/microsoft/git-base-coco</footnote>
ones, for approximate retrieval when adding LSH<sub>256</sub> to
LoGG3D-Net. Globally, DSI-3D with Hilbert curve index-
ing 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 at least as ef-
fective as a conventional state-of-the-art approximate ap-
proach. In the following section, we discuss its superiority
facing the questions of complexity and retrieval time.

## 5.3 Complexity and retrieval time

In its current implementation [24], retrieval with LoGG3D-Net is performed over the entire reference dataset by sequential comparisons (first line of Tables 2 and 3). This makes the retrieval time proportional to the size of the dataset (n) with a time complexity $O(n)$. The state-of-the-art solutions listed in Section 2.1 proceed in the same way. The similarity search in such high-dimensional spaces can be accelerated with indexes such as the LSH [15], as experimented in the same Tables (lines 2 and 3). The complexity largely differs from the variant used but is generally dominated by $O(n^ρ)$ with $0 ≤ ρ ≤ 1$, under the approximate retrieval assumption. In contrast, DSI-3D relies on model inference with constant $O(1)$ complexity, which is a significant advantage facing large datasets of point clouds. It also works under the approximate retrieval paradigm. However, as we have experimented in the previous section, the retrieval quality remains fully comparable to the ones of other solutions under the same paradigm.

In terms of retrieval time, the exact LoGG3D-Net, in its
public implementation, ranges from 0.0003 to 0.0093s in
average for all the queries. LoGG3D-Net with LSH<sub>256</sub> is
5.98 times faster, while LoGG3D-Net with LSH<sub>32</sub> is 7.20
times faster (but with a poor retrieval quality).

For DSI-3D indexed with *Positional Structured identifiers*, currently retrieval time is 0.09s, 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 LoGG3D-Net ($T = 0.67N_{desc} - 0.68$). This allows us to estimate that the inversion point occurs at $N_{desc} = 135.3e3$ descriptors in favor of DSI-3D. According to the settings used, this amount roughly corresponds to a spatial coverage of 10km², at which point DSI-3D would become faster in its current 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 strate-
gies, 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.

# 6 Conclusion

In this article, we have presented DSI-3D, a new indexing
and retrieval approach for 3D point clouds. It drastically
accelerates retrieval, compared to current literature which
mainly focuses on point cloud description and performs re-
trieval following a linear time complexity as experimented
here, it can be slightly improved with off-the-shelf index
such as LSH. The proposal relies on the adaptation of the
Differentiable Search Index, but also introduces two new
*Positional Structured identifiers*, fitted for the problem of
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. In the future,
it will be necessary to continue the experiments, in par-
ticular by varying the model parameters further, and also
by considering larger datasets to confirm its robustness in
terms of the quality of the returned responses, its optimality
in terms of response time, following a constant complexity,
having been proven.

7 Acknowledgments

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).

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] Nicola De Cao, Gautier Izacard, Sebastian Riedel, and Fabio Petroni. Autoregressive entity retrieval. *arXiv preprint arXiv:2010.00904*, 2020.

[3] 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.

[4] 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.

[5] 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.

[6] 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.
[7] 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.

[8] 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.

[9] Giseop Kim and Ayoung Kim. Scan context: Ego-centric 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.

[10] 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.

[11] Peihua Li, Jiangtao Xie, Qilong Wang, and Wangmeng Zuo. Is second-order information helpful for large-scale visual recognition? In Proceedings of the IEEE international conference on computer vision, pages 2070–2078, 2017.

[12] Zhe Liu, Shunbo Zhou, Chuanzhe Suo, Peng Yin, Wen Chen, Hesheng Wang, Haoang Li, and Yun-Hui Liu. Lpd-net: 3d point cloud learning for large-scale place recognition and environment analysis. In Proceedings of the IEEE/CVF international conference on computer vision, pages 2831–2840, 2019.

[13] 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.

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

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

[16] 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.

[17] 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.

[18] 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.

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

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

[21] 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.

[22] 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.

[23] 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.

[24] 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.

[25] 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.

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

[27] 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.