# CANDY: A Benchmark for Continuous Approximate Nearest Neighbor Search with
Dynamic Data Ingestion

Xianzhi Zeng1, Zhuoyan Wu2, Xinjing Hu3, Xuanhua Shi3, Shixuan Sun4, Shuhao
Zhang5
1Singapore University of Technology and Design, 2National University of
Singapore,
3Huazhong University of Science and Technology, 4Shanghai Jiao Tong
University,
5Nanyang Technological University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

Approximate K Nearest Neighbor (AKNN) algorithms play a pivotal role in
various AI applications, including information retrieval, computer vision, and
natural language processing. Although numerous AKNN algorithms and benchmarks
have been developed recently to evaluate their effectiveness, the dynamic
nature of real-world data presents significant challenges that existing
benchmarks fail to address. Traditional benchmarks primarily assess retrieval
effectiveness in static contexts and often overlook update efficiency, which
is crucial for handling continuous data ingestion. This limitation results in
an incomplete assessment of an AKNN algorithm’s ability to adapt to changing
data patterns, thereby restricting insights into their performance in dynamic
environments. To address these gaps, we introduce CANDY, a benchmark tailored
for Continuous Approximate Nearest Neighbor Search with Dynamic Data
Ingestion. CANDY comprehensively assesses a wide range of AKNN algorithms,
integrating advanced optimizations such as machine learning-driven inference
to supplant traditional heuristic scans, and improved distance computation
methods to reduce computational overhead. Our extensive evaluations across
diverse datasets demonstrate that simpler AKNN baselines often surpass more
complex alternatives in terms of recall and latency. These findings challenge
established beliefs about the necessity of algorithmic complexity for high
performance. Furthermore, our results underscore existing challenges and
illuminate future research opportunities. We have made the datasets and
implementation methods available at: https://github.com/intellistream/candy.

##  1 Introduction

Approximate K Nearest Neighbor (AKNN) search algorithms underpin many AI
applications, including information retrieval [29], computer vision [8], and
natural language processing [25]. These algorithms support essential functions
like real-time decision-making, image recognition, and semantic understanding
[19, 20]. AKNN algorithms have evolved significantly since their initial
proposal in 1998 [16]. Early developments focused on optimizing search
efficiency and accuracy through various techniques such as locality-sensitive
hashing (LSH)[13], tree-based indexing[37], and graph-based methods [28],
primarily for static datasets. Despite their importance, the evolving nature
of real-world data presents significant challenges not adequately addressed by
current benchmarks, which predominantly assess AKNN algorithms in static
environments, focusing on retrieval effectiveness while largely ignoring
update efficiency critical for ongoing data ingestion [23, 36, 21]. This
oversight results in an incomplete understanding of an AKNN algorithm’s
adaptability and performance in environments where it must continuously update
and perform searches amid dynamic data ingestion.

Recognizing the limitations of traditional AKNN algorithms, there has been a
recent shift towards adapting these methods for more realistic, continuously
evolving data streams. The foundational work by Sundaram et al.[34] first
explored dynamic data ingestion in AKNN, investigating the incremental nature
of Locality-Sensitive Hashing (Lsh [13]). Following this, onlinePQ [39]
introduced incremental clustering to Product Quantization (Pq [17]) to
dynamically adjust Pq data structures as new information arrives. Researchers
have also explored accommodating proxy graphs of AKNN, such as the
Hierarchical Navigable Small Worlds (Hnsw [28]), for incremental vector
additions. Notably, the SSD-aware framework “Freshdiskann”[33] investigates
vector compression and SSD-aware optimizations to support incremental vector
additions. Recent developments by Aguerrebere et al.[3] further enhance AKNN
algorithms with vector compression optimizations, marking significant progress
in adapting AKNN algorithms to dynamic data ingestion.

However, the current literature [23, 36, 21, 19] still largely overlooks
comprehensive methodologies for evaluating the efficiency and adaptability of
AKNN algorithms in environments characterized by continuous updates and
distribution shifts [3, 33] due to dynamic data ingestion. This gap is
particularly evident in scenarios like online news aggregators, where the need
to adapt content recommendations in response to new articles and shifting user
interactions highlights the inefficiencies of AKNN algorithms in updating
indices with fresh data, potentially leading to stale recommendations and
degraded user experiences. Such dynamics underscore a critical gap in existing
benchmarking approaches and highlight the urgent need for new benchmarks that
rigorously evaluate the resilience and adaptability of AKNN algorithms to meet
the demands of modern, real-time digital ecosystems.

Figure 1: Overview of the CANDY benchmark framework.

Our Contributions: In response to the pressing need for benchmarks that
effectively evaluate AKNN algorithms in dynamic data ingestion contexts, we
have developed CANDY, a comprehensive benchmark framework (Figure 1). Our
contributions are articulated across several dimensions:

  * •

We introduce a novel categorization of state-of-the-art AKNN algorithms into
two principal types: ranging-based and navigation-based. This classification
facilitates a deeper understanding of the operational dynamics of these
algorithms.

  * •

We propose specific adaptations to improve the performance of AKNN algorithms,
enabling them to continuously adapt to dynamic data ingestion. We have also
implemented optimizations that significantly boost both the efficiency and
accuracy of these algorithms across various data conditions.

  * •

CANDY incorporates advanced data handling strategies such as data dropping and
micro-batching, which simulate real-world dynamic data ingestion. This setup
facilitates rigorous testing of AKNN algorithms under realistic rates and
conditions. Furthermore, to explore the effects of distribution shifts, we
have developed a novel synthetic dataset WTE.

  * •

Utilizing CANDY, our experimental studies provide novel insights into the
adaptability and overall performance of AKNN under the aforementioned common
concerns, i.e., the _continuous updates_ and _distribution shifts_. We further
examine the effectiveness of _AKNN optimizations_ and other important
configurations such as micro-batching.

##  2 CANDY Benchmark Framework

We now present CANDY, a benchmark for evaluating continuous AKNN with dynamic
data ingestion.

###  2.1 Data Handling

#### Datasets

Consistent with methodologies from previous research [23, 3], we utilize a
variety of real-world workloads spanning multiple application domains,
including text embedding (Glove, DPR), image processing (SIFT, Sun, Trevi),
and audio (Msong). We also incorporate the Random synthetic dataset from
LibTorch [32], which offers adjustable dimensions and volumes of vectors and
employs the _torch::rand_ function to generate identically distributed
(i.i.d.) uniform values between $0$ and $1$. Recognizing that the performance
of AKNN algorithms can be markedly influenced by drifts in data distribution
[3], such as evolving news topics, we have developed the WTE dataset to
effectively simulate these dynamic changes. Derived from nouns categorized as
land vehicles and aircraft in the War Thunder game wiki [2], WTE uses these
nouns to create synthetic sentences, subsequently encoded into vectors via the
DPR methodology [3]. This dataset allows for the adjustment of drift starting
positions by altering the onset of new noun categories and enables the
modulation of drift intensities through controlled word contamination, with
the magnitude dictated by predefined probabilities. More details can be found
at Appendix A.1.

#### Ingestion Admission Control

The rapid influx of data, such as high-rate tweets [34, 1], imposes
significant time and computational constraints on processing capabilities.
These constraints, often overlooked in AKNN literature, critically hinder the
system’s ability to maintain an up-to-date index. If the processing speed of
AKNN algorithms lags behind the incoming data flow, an unmanageable backlog
may develop, potentially growing indefinitely [7, 4, 10, 5]. Pausing data
input to clear the backlog is impractical due to limited storage for pending
data, forcing the system to discard incoming information. This often results
in decreased accuracy and reduced search efficiency. To accurately simulate
this challenge, CANDY includes a specific ingestion admission control
protocol. This protocol utilizes a high-resolution clock to regulate data
release at a constant rate, typically set at 4,000 rows per second by default.
If AKNN processes data more slowly than this rate, excess data is naturally
dropped due to congestion, mirroring realistic operational constraints.

#### Micro-Batching

The data science community recognizes the significant advantages of micro-
batching for effectively processing large datasets, though the specific
motivations and purposes for its use can vary. Micro-batching divides
extensive datasets into smaller, manageable units, enabling more frequent
updates to machine learning model parameters and thus promoting quicker model
convergence [15, 40]. On the other hand, accumulating data in larger batches
instead of processing streams immediately can greatly improve the throughput
of online database systems [43]. Inspired by these insights, we have
integrated adaptable micro-batch mechanisms into CANDY, allowing for the
aggregation of continuously ingested data streams into batches with
configurable sizes.

###  2.2 Categorization, Adaptation, and Optimization

AKNN aims to efficiently identify the k _closest_ vectors to a query $Q$ from
a set, $S$. AKNN algorithms optimize search processes by selecting a strategic
subset of vectors, $C$ (i.e.,
$\hyperref@@ii[tab:notations]{C}\subseteq\hyperref@@ii[tab:notations]{S}$),
which significantly enhances data retrieval efficiency compared to exhaustive
search baseline (denoted as Baseline). Common distance measures include L2
distance [23] and inner product distance [3], and both are implemented in
CANDY and inner product is used unless mentioned otherwise.

#### Algorithm Categorization

We classify AKNN algorithms into two main categories based on their subset
selection techniques: _ranging-based_ and _navigation-based_. This
classification helps assess how different AKNN strategies manage the trade-
offs between computational overhead and accuracy. The performance and
adaptability of each category are thoroughly evaluated and summarized in Table
1, providing insights into their effectiveness in handling real-time data
variations.

_1) Ranging-based AKNN:_ Ranging-based AKNN involves pre-computed division of
$S$ into distinct ranges, irrespective of the specific $Q$. It segments $S$
into disjoint ranges such as $D_{1},D_{2},\ldots,D_{n}$. Upon receiving a $Q$,
$C$ is selected from one or a combination of these ranges (e.g.,
$\hyperref@@ii[tab:notations]{C}=D_{1}$ or
$\hyperref@@ii[tab:notations]{C}=D_{1}\cup D_{2}$). CANDY includes a spectrum
of ranging-based AKNN algorithms, from traditional approaches like Lsh to
those specially designed for dynamic data scenarios, such as onlinePQ.

_2) Navigation-based AKNN:_ Navigation-based AKNN establishes navigational
links within $S$, associating each vector with its similar counterparts,
typically through a proximity graph. Unlike the static pre-computed ranges of
the ranging-based approach, the subset $C$ for each query is dynamically
assembled by iteratively navigating from one vector to its neighboring
vectors. Key variations among navigation-based AKNN methods include their
strategies for navigating and deciding when to cease expanding the pool of
candidate neighbors. Prominent implementations in CANDY feature the K-Nearest
Neighbor Graph (Nndecent) and hierarchical approximate Delaunay Graph (Hnsw).

Category | Algorithm Name | Descriptions
---|---|---
Ranging-based |  Lsh [13] | Data-independednt hashing to determine ranges
Flann [31] | Space partition to determine ranges
Pq [17] | Product quantization to determin ranges
Ivfpq [17] | Hierachical optimization over Pq
onlinePQ [39] | Incrementally update centroids of Pq
Navigation-based |  Nsw [27] | Delaunay Graph for navigation
Nndecent [9] | K-Nearest Neighbor Graph for navigation
Dpg [23] |  | K-Nearest Neighbor Graph and Relative Neighborhood Graph
---
for navigation
Nsg [11] |  | Optimized vertex assignment compared with Dpg
---
Hnsw [28] | Hiearchical construction of Nsw
Lshapg [44] | Using the hashing of Lsh to optimize graph construction

Table 1: Representative AKNN algorithms and their categories.

#### Adapting to Dynamic Data Ingestion

We discuss the adaptation of AKNN algorithms to dynamic data ingestion,
highlighting three distinct approaches:

_1) Minimal Adaptation Required:_ Algorithms such as Lsh, Nsw, Hnsw and Lshapg
inherently support incremental updates and are thus naturally suited for
dynamic data environments. onlinePQ, designed explicitly for dynamic
ingestion, fits seamlessly with minimal modifications needed. For these
algorithms, adaptation primarily involves aligning their API and I/O
structures within our codebase to ensure compatibility.

_2) Adaptation with Enforced Assumptions:_ Pq and Ivfpq process data
incrementally but depend on a pre-existing understanding of data
distributions, typically acquired through extensive preliminary data scanning.
This process, while intensive, is necessary to set up the initial knowledge
base used during dynamic ingestion. In our framework, we establish this
knowledge base during an offline stage and maintain the assumption that it
remains valid in dynamic contexts. We exclude any overhead from this setup
phase in our performance evaluations to focus on real-time processing
capabilities.

_3) Substantial Algorithm Modifications:_ Algorithms like Nndecent, Dpg, and
particularly Nsg, initially designed for static datasets, require
comprehensive modifications to accommodate dynamic data ingestion. Nndecent
originally constructs a neighborhood graph offline, with each node maintaining
its closest k nodes in a heap. For dynamic adaptation, we have integrated
online query and update capabilities. The online query algorithm initiates
from a randomly selected node, employing a greedy strategy to converge towards
the target region while maintaining a heap of candidate nodes for iterative
expansion. Online insertion involves identifying and updating the neighbors of
the newly inserted node through this online search mechanism, effectively
embedding the node into the graph. Online deletions are managed by marking
nodes in a deleted set, thus excluding them from query results without
physically removing them from the graph.

Dpg builds upon the neighborhood graph to create layered structures. It
modifies the initial graph (layer0) by selecting only half of each node’s
neighbors based on directional diversity rather than distance, aiming to
disperse neighbors across various directions and maintaining bidirectional
connectivity. The query process mirrors that of Nndecent, targeting the
modified graph (layer1). The online insertion updates both layers: it first
updates layer0 with new neighbors as identified by the online search and then
adjusts layer1 neighbors for the newly inserted node using a $O(K^{2})$
selection algorithm. If a node becomes a neighbor in layer0, it is also
updated in layer1, either by direct addition if there is capacity or by
replacing an existing neighbor if the displaced relationship is also reflected
in layer1.

Nsg uses a pre-built graph based on brute force. Adapting Nsg for dynamic use
involves integrating newly ingested data points into the existing graph
structure. Specifically, each new point undergoes a global search for
neighbors starting from a designated navigation point, similar to the initial
build phase. This process ensures that the graph remains navigable and that
new points are appropriately linked to maintain the integrity and efficiency
of the graph, allowing the algorithm to continue to function effectively as
new data is ingested.

#### Optimization Techniques

Recent AKNN optimization techniques are diverse but can be strategically
categorized into two main types: machine learning and optimized distance
computation [22, 38, 6, 3, 12]. Each technique is designed for specific AKNN
algorithms or distance metrics, and both are integrated into CANDY.

_1) Machine learning-based optimizations_ are employed for both ranging-based
[22, 38] and navigation-based [6] AKNN algorithms. These optimizations
typically replace costly heuristic scans or vector data traversals with more
efficient machine learning inferences, transforming data access overhead into
computationally cheaper mathematical calculations [21]. CANDY, leveraging the
LibTorch/PyTorch ecosystem, supports standard neural network modules derived
from _torch::nn::Module_ , tensor-based loss functions, and commonly used
optimizers such as _torch::optim::Adam_. This flexibility facilitates the
exploration of advanced machine learning techniques to further enhance AKNN
performance.

_2) Distance computation optimization_ is another crucial strategy [3, 12].
The objective is to minimize the computational load associated with
calculating and comparing distances among vectors, a significant bottleneck in
many AKNN applications. Techniques such as randomized calculations [12] and
data compression [3] are implemented to reduce these overheads effectively.
Together, these optimization strategies provide a comprehensive approach to
refining the efficiency and accuracy of AKNN algorithms within CANDY.

###  2.3 Performance Evaluation Metrics

Following established methodologies [23, 12, 21], we employ _query recall_
($r$) to evaluate the accuracy of AKNN algorithms. Query recall measures the
proportion of the true nearest neighbors that are correctly identified by the
algorithm from all possible true nearest neighbors. Specifically, if the set
of nearest neighbors identified by AKNN is $O_{aknn}$, and the exact set of
nearest neighbors is $O_{exact}$, then $r$ is defined as
$\hyperref@@ii[tab:notations]{r}=\frac{|\hyperref@@ii[tab:notations]{O_{aknn}}\cap\hyperref@@ii[tab:notations]{O_{exact}}|}{|\hyperref@@ii[tab:notations]{O_{exact}}|}$.
By default, we report the recall for retrieving the top 10 nearest vectors for
each of 100 input queries, denoted as _recall@10_ in following [3].
Additionally, we assess the efficiency of AKNN algorithms using _query
latency_ , which measures the elapsed time from the submission of a query to
when AKNN returns the results [23, 12, 21]. Importantly, we exclude any setup
overhead incurred during offline stages, such as loading initial data or
preparing data structures, from this metric. This exclusion ensures that our
latency measurements reflect only the real-time processing capabilities of the
AKNN algorithms.

###  2.4 Summary of Differences from Static Data Scenarios

Our research deviates from traditional AKNN evaluations, which typically
preload all data during an offline stage without subsequent updates to the
data storage. Unlike these conventional setups referenced in prior studies
[23, 13, 17, 31, 39, 27, 23, 11], we examine the impact of dynamic data
ingestion on AKNN performance. Our methodology starts with an initial dataset
loaded into AKNN, then transitions to a phase of continuous online data
feeding, mimicking real-world scenarios where data is not static but
constantly arriving. This setup allows us to explore operational challenges
unique to dynamic environments, such as data overflow and the processing
demands of simultaneous data ingestion and query handling, which can degrade
query recall and increase latency.

##  3 Experiments and Observations

In this section, we detail our experimental approach using the CANDY framework
to assess how AKNN algorithms perform when subjected to continuous data flow.
Note that, we have adhered to recommended default settings from prominent
studies [13, 17, 31, 39, 27, 23, 11, 44], validated to balance accuracy and
efficiency, without specifically tuning any algorithm to maximize recall or
minimize latency [23].

###  3.1 Poor Ingestion Efficiency is a Severe Common Bottleneck

We first investigate how different AKNN algorithms performs under real-world
datasets, concerning both query latency and query recall, as summarized in
Table 2.

> Observation 1. Contrary to common belief [23], none of the evaluated AKNN
> outperforms the brutal force approach with dynamic data ingestion. This is
> majorly due to the large overhead of pending writings in AKNN.

Algorithms | Recall@10 | Query Latency ($\times 1000ms$)
---|---|---
Glove | SIFT | Msong | Sun | DPR | Trevi | Glove | SIFT | Msong | Sun | DPR | Trevi
Baseline | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.43 | 0.44 | 0.60 | 0.69 | 0.76 | 2.53
Ranging-based | Lsh | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 | 0.07 | 0.17 | 0.22 | 0.23 | 0.42 | 0.19 | 11.96
Flann | 0.01 | 0.01 | 0.01 | 0.00 | 0.00 | 0.11 | 1.09 | 1.18 | 1.85 | 1.65 | 1.27 | 2.69
Pq | 0.09 | 0.22 | 0.50 | 0.42 | 0.09 | 0.38 | 354.43 | 351.58 | 358.40 | 363.92 | 361.51 | 414.77
Ivfpq | 0.03 | 0.23 | 0.01 | 0.33 | 0.11 | 0.28 | 393.40 | 2.11 | 400.55 | 2.85 | 409.62 | 504.46
onlinePQ | 0.12 | 0.31 | 0.78 | 0.43 | 0.09 | 0.38 | 1.60 | 1.20 | 3.36 | 384.48 | 395.55 | 19.20
Navigation-based | Hnsw | 0.39 | 0.54 | 0.61 | 0.77 | 0.46 | 0.51 | 117.76 | 15.86 | 151.58 | 584.71 | 691.58 | 13466.48
Nsw | 0.10 | 0.35 | 0.28 | 0.63 | 0.33 | 0.51 | 1883.68 | 233.17 | 454.67 | 770.08 | 1190.43 | 7048.91
Nsg | 0.01 | 0.01 | 0.00 | 0.02 | 0.01 | 0.03 | 30.62 | 323.19 | 401.75 | 46.20 | 48.51 | 1262.32
Nndecent | 0.01 | 0.12 | 0.00 | 0.23 | 0.17 | 0.46 | 30.58 | 15.38 | 5.34 | 6.61 | 40.38 | 20.23
Dpg | 0.08 | 0.33 | 0.06 | 0.30 | 0.31 | 0.48 | 18.81 | 19.79 | 614.12 | 692.44 | 87.52 | 5547.55
Lshapg | 0.11 | 0.10 | 0.49 | 0.30 | 0.11 | 0.42 | 11.52 | 4.72 | 20.20 | 27.90 | 8.14 | 22.37

Table 2: Comparing AKNN algorithms with dynamic data ingestion.

We observe that Lsh surpasses Baseline in terms of query latency on certain
datasets, achieving up to 75% reduction on DPR. However, its accuracy is
significantly lower, with a maximum recall of only 0.01, rendering it too
imprecise for practical application. In contrast, onlinePQ and Hnsw
demonstrate the highest accuracy among ranging-based and navigation-based AKNN
algorithms, respectively, with recalls reaching as high as 0.7. Despite their
superior accuracy, these algorithms exhibit considerably higher query
latencies compared to Baseline; for instance, Hnsw’s latency is 908 times
greater on DPR.

Algorithms | Propotion of PWL (%) | PWL ($\times 1000ms$) | VSL ($\times 1000ms$)
---|---|---|---
Msong | DPR | Trevi | Msong | DPR | Trevi | Msong | DPR | Trevi
Baseline | 73.13 | 63.32 | 59.96 | 0.44 | 0.48 | 1.51 | 0.16 | 0.28 | 1.01
Ranging-based | Lsh | 74.99 | 89.10 | 1.11 | 0.17 | 0.17 | 0.13 | 0.06 | 0.02 | 11.83
Flann | 98.99 | 98.14 | 97.48 | 1.83 | 1.24 | 2.62 | 0.02 | 0.02 | 0.07
Pq | 99.55 | 99.61 | 99.53 | 356.80 | 360.10 | 412.80 | 1.60 | 1.40 | 1.97
Ivfpq | 99.52 | 99.55 | 99.16 | 398.64 | 407.78 | 500.24 | 1.92 | 1.83 | 4.22
onlinePQ | 94.38 | 99.14 | 99.15 | 3.17 | 392.14 | 19.03 | 0.19 | 3.41 | 0.16
Navigation-based | Hnsw | 99.96 | 88.94 | 86.87 | 151.52 | 615.08 | 11698.58 | 0.06 | 76.49 | 1767.90
Nsw | 99.98 | 90.48 | 88.04 | 454.59 | 1077.06 | 6205.80 | 0.09 | 113.37 | 843.11
Nsg | 94.33 | 99.94 | 94.80 | 378.95 | 48.48 | 1196.68 | 22.80 | 0.03 | 65.63
Nndecent | 98.77 | 98.83 | 97.46 | 5.27 | 39.90 | 19.71 | 0.07 | 0.47 | 0.51
Dpg | 98.26 | 99.33 | 98.29 | 603.45 | 86.93 | 5452.70 | 10.67 | 0.59 | 94.85
Lshapg | 80.96 | 93.15 | 94.20 | 16.36 | 7.58 | 21.07 | 3.85 | 0.56 | 1.30

Table 3: Break down the query latency into pending write latency and vector
search latency. “PWL” is short for pending writing latency, and “VSL” is short
for vector search latency.

In Table 3, query latency is segmented into two distinct components for
clearer analysis: _pending writing latency_ , which accounts for the time
spent waiting for ongoing data writes to complete, and _vector search latency_
, which measures the time taken for vector search operations after AKNN has
processed pending writes. Msong, DPR, and Trevi are used as example datasets,
with similar observations noted for other datasets, though these results are
omitted. Two primary insights emerge from this analysis. First, for the
majority of AKNN algorithms across most datasets, pending writing latency
constitutes the larger portion of total query latency. For example, in
onlinePQ and Hnsw, pending writing accounts for over 94% and 86% of the total
query latency, respectively. This indicates that pending writing is a
significant bottleneck in the performance of query processing. Second, while
the vector search latency for some AKNN algorithms is lower than that of
Baseline in certain datasets, this advantage is not consistent across all
datasets. For instance, in the Msong dataset, Hnsw reduces vector search
latency by 62% compared to Baseline, with a reasonable recall of 0.61, as
shown in Table 2. However, in the DPR and Trevi datasets, Hnsw exhibits vector
search latencies that are $271\times$ and $1766\times$ longer than Baseline,
respectively. This inconsistency can be attributed to the dropping of critical
data during ingestion, which complicates the navigation process and thereby
increases the latency.

###  3.2 Most AKNN Acts Poorly Towards Distribution Drifts

We next examine the impacts of distribution drifts, focusing specifically on
the effects of drift occurrence position and general intensity of distribution
drifts, which we analyze individually. Our evaluations are conducted using our
novel datasets WTE.

> Observation 2. Most AKNNs except Hnsw are challenged by distribution drifts.
> Despite the resilience, the ingestion bottleneck of Hnsw is affected by the
> distribution shift and further complicated by the semantic relevance of
> data.

(a) Query Recall

(b) Query Latency.

Figure 2: Tuning the occurrence position of distribution drift. The Red dashed
line indicates where the distribution drift occurs exactly at the same place
as the beginning of online ingested data.

Figure 3: Tuning the intensity of distribution drift. A larger contamination
probability indicates higher intensity.

To investigate the impact of distribution drifts on AKNN algorithms, we varied
the occurrence positions of drifted noun dictionary lists from 1,000 to
90,000. The resulting query recall and latency metrics are illustrated in
Figure 3. Notably, drifts occurring before the 50,000 mark tend to be
recognized during the offline initial data loading phase by AKNN algorithms,
influencing their subsequent online performance.

Among the algorithms evaluated, Hnsw shows the highest resilience, maintaining
a recall rate above 0.4, despite slight fluctuations in both latency and
recall. These fluctuations arise primarily from how Hnsw adapts to the
significant dissimilarities between embedding vectors before and after the
drift. It may either create a new graph cluster for the drifted data, which is
efficient and precise, or try to integrate it into the existing graph
structure, which can lead to higher costs and inaccuracies due to unnecessary
traversals through irrelevant graph vertices. This tension between integration
and segregation is the main cause of the observed variability in its
performance.

In contrast, all other evaluated AKNN algorithms struggle to achieve a recall
rate above 0.1 when faced with distribution drifts. In particular, despite
onlinePQ’s design intentions to adapt dynamically to changing conditions, its
simplistic update rule falls short, leading to suboptimal performance that is
even less effective than Pq. It fails to harmonize the original and new data
distributions effectively, resulting in a compromised state where neither old
nor new data is accurately processed or indexed. Ivfpq, a ranging-based AKNN,
shows substantial fluctuations in performance, especially when the drift
occurs early in the data ingestion process. Its dependence on a fixed data
distribution and pre-trained cluster centroids makes it particularly
vulnerable to changes. This effect is exacerbated by its hierarchical design,
which amplifies the fluctuation compared to Pq.

We next investigated how varying the intensity of distribution drifts, by
adjusting the probability of word contamination from 0 to 0.8, affects query
recall. These results are presented in Figure 3. The query latency, similar to
evaluations on the DPR dataset (Table 2), showed marginal fluctuations across
algorithms, with deviations no greater than 5%. Across the board, most AKNN
algorithms exhibited low recall rates and higher latency, with recalls
consistently under 0.4, except for Hnsw. Notably, Hnsw’s recall improved as
the drift intensity increased, which can be credited to its robust
hierarchical structure and adaptive heuristics. This algorithm effectively
clusters drift-related data around hot-spot topics within its proxy graph,
enhancing its capability to retrieve relevant entries. This process is
optimized by its hierarchical design, which manages the scope of each cluster,
reducing the likelihood of including irrelevant results and thus boosting
accuracy.

To further analyze Hnsw, we decompose its data ingestion process into three
distinct parts: 1) _Greedy_ , which involves the greedy search to identify the
insertion region; 2) _Candidate_ , which narrows down the connecting data
points; and 3) _Link_ , which connects the selected candidates with the new
data. We examine different datasets, DPR and WTE, across various word
contamination probabilities (ranging from 0 to 0.8), with the time breakdown
illustrated in Figure 5. As expected, the distribution shift (WTE) results in
a larger proportion of time spent on _Candidate_ compared to the no shift
scenario (DPR), as identifying close data point regions becomes more
challenging under the shift. Additionally, the proportion of time spent on
_Link_ decreases when the data is less semantically relevant. Specifically,
DPR, generated from a real-world corpus, is more semantically relevant than
WTE, which comprises fabricated sentences. The semantic relevance of WTE also
increases slightly with higher word contamination.

Figure 4: Breakdown of Hnsw on DPR and WTE.

(a) Query Recall

(b) Query Latency.

Figure 5: Tuning the size of micro-batches from 200 to 50000.

###  3.3 Micro-Batch Size Tuning is a Hard Game

Our experiments with varying micro-batch sizes from 200 to 50,000 in the
context of the DPR datasets demonstrated notable impacts on query latency and
recall, with results presented in Figure 5. These findings underscore that
there is no universally optimal batch size that suits all AKNN algorithms.

> Observation 3. Micro-batch size significantly affects AKNN performance, and
> the optimal setting varies by algorithm.

The efficiency of batch processing is highly dependent on the specific AKNN
algorithm used. For algorithms that process vector points individually, such
as Hnsw, Nsw, and Nsg, larger batch sizes tend to reduce processing
efficiency, consequently increasing query latency as shown in Figure 5(b). In
contrast, algorithms like Lsh demonstrate optimal performance at a moderate
batch size—around 1,000—balancing the benefits of data aggregation with
processor utilization.

Additionally, our experiments revealed that batch size profoundly impacts
query recall, particularly through its influence on data ingestion efficiency
and the likelihood of data droppings (Figure 5(a)). Smaller batch sizes, while
seemingly agile, often lead to higher data loss when system capacity is
exceeded, as evidenced by increased inaccuracies in Baseline ’s performance,
which is typically expected to execute exact searches. Larger batch sizes
mitigate this risk by reducing the time spent segmenting ingested data and
minimizing static overhead, thereby preserving more complete data sets and
enhancing recall across all tested algorithms.

###  3.4 Optimizations are Promising, but There are Still Open Challenges.

This section evaluates AKNN optimizations, encompassing both machine learning-
based enhancements and optimized distance computation strategies. These
optimizations are tested using representative algorithms Lsh and Hnsw,
respectively, under conditions that include steady and shifted data
distributions using datasets DPR and WTE. Please refer to Appendix A.4 for
more setup details. Results are summarized in Table 4.

> Observation 4. Machine learning leads to large improvements of AKNN due to
> better data organization, but is challenged by distribution shifts.

Machine learning (ML) significantly improves AKNN performance through enhanced
data organization, as observed with Lsh in our experiments. By integrating a
simple MLP model for hashing, trained offline to mimic spectral hashing loss
functions, we achieved a $7\times$ increase in accuracy. However, this method
incurs higher query and vector search latencies due to its computational
overhead. Interestingly, machine learning reduced pending writing latency by
66%, optimizing vector assignments and thus improving overall efficiency.
Despite these gains, machine learning struggles under dynamic conditions with
data distribution shifts, leading to exhaustive searches across all buckets
and even higher operational costs than Baseline.

Algorithms | Not Drift | With Drift
---|---|---
Recall | QL | VSL | PWL | Recall | QL | VSL | PWL
Baseline | 1.000 | 0.19 | 0.12 | 0.07 | 1.000 | 0.21 | 0.14 | 0.07
ML |  Lsh w/o ML | 0.003 | 0.03 | 0.01 | 0.03 | 0.003 | 0.04 | 0.01 | 0.03
Lsh w/ ML | 0.024 | 0.10 | 0.10 | 0.01 | 0.374 | 5.82 | 5.82 | 0.01
DCO | Hnsw | 0.41 | 485.53 | 47.78 | 437.75 | 0.48 | 113.82 | 11.26 | 102.56
Hnsw w/ comp. | 0.30 | 99.32 | 0.08 | 99.24 | 0.09 | 15.41 | 0.07 | 15.34
Hnsw w/ rand. | 0.42 | 87.58 | 0.09 | 87.49 | 0.39 | 123.51 | 11.45 | 112.06

Table 4: Combined results for AKNN with machine learning (ML) and distance
computation optimizations (DCO). “QL” is short for query latency, “VSL” is
short for vector search latency, and “PWL” is short for pending writing
latency. The unit of latency is $\times 1000ms$.

> Observation 5. Optimized distance computation is also helpful, but more
> awareness should be put into solving the ingestion efficiency challenge.

Distance computation optimizations (DCO) include data compression (comp.) and
randomized calculations (rand.). These methods proved beneficial, reducing
query latency by up to 81.7% when using compression techniques such as
Locally-Adaptive Vector Quantization when applied to Hnsw in our study as an
example. However, challenges persist with ingestion efficiency, preventing
optimized AKNNs from surpassing the query latency performance of Baseline.
Inefficient data ingestion impacts the resilience of optimizations against
data distribution shifts, as seen with compression where recall significantly
dropped from 0.48 to 0.09 under shifted conditions. Specifically, the
countermeasures against distribution shifts like [3] are hindered by an
insufficient sample size due to data dropping, leading to their
ineffectiveness. On the other hand, randomized calculation increases latency
in comparison to Hnsw. This is because it tends to cause Hnsw to become mired
in clusters of poorly ingested, distant data points when data dropping and
distribution shifts coincide. This issue highlights the critical need for
improving ingestion efficiency to leverage the full potential of AKNN
optimizations in dynamic environments.

##  4 Limitations

The limitations of CANDY are outlined as follows: First, CANDY operates under
single-threaded, in-memory, and CPU-only conditions, not yet harnessing
advances such as SSDs [33] and GPUs [22] that could boost AKNN performance.
Exploring these technologies is a crucial direction for future research.
Despite incorporating an implementation of parallel and distributed computing
based on frameworks by Wang et al. [35] and Moritz et al. [30] in CANDY, no
significant new insights have emerged due to the shared-nothing architecture
of the data shards. Second, CANDY does not support dynamic deletion due to the
complexities of data expiration and resource recycling as highlighted by Singh
et al. [33]. Efficiently managing and recycling outdated information within
dynamic environments presents challenges that complicate the direct
application of deletion processes, impacting both system performance and data
integrity. Third, the scope of CANDY’s evaluation is not yet extended to the
accuracy of downstream tasks like Retrieval-Augmented Generation (RAG). This
limitation is due to the specialized nature of these downstream tasks, which
involve additional complexities beyond the primary objectives of this
benchmark. While these tasks are crucial, as noted in the works of Lyu et al.
[26] and Jiang et al. [18], addressing them requires a distinct set of
methodologies and metrics that fall outside the current scope of CANDY.
Lastly, concerning data handling within CANDY, assumptions about data arrival
are overly simplified—data is expected to arrive in order and at a constant
speed. This setup does not account for more realistic, complex scenarios
involving out-of-order or skewed data distributions that are increasingly
common in real-world applications. Addressing these challenges, as explored by
Heliou et al. [14], Zeng et al. [41] and Zhang et al. [42], involves intricate
strategies for error compensation and load balancing, which we aim to
incorporate in future iterations of our benchmark.

##  5 Conclusion

In this paper, we introduced CANDY, a benchmark that goes beyond traditional
static data scenarios, offering a deep dive into the performance of AKNN
algorithms under conditions of continuous data ingestion. CANDY is publicly
available and is compatible with LibTorch/PyTorch, promoting collaborative
innovation within the machine learning and data management communities. Our
experimental analysis using CANDY has shed light on unique challenges faced in
dynamic data contexts, particularly the efficiency of data ingestion and the
significant effects of data distribution shifts on AKNN performance.
Furthermore, CANDY elucidates complex factors like micro-batching
configurations and evaluates the extent and limitations of existing AKNN
optimizations. The insights gained from this benchmark are poised to drive
forward research into more efficient AKNN workflows and the development of
advanced machine learning strategies better suited for managing data dynamics.
We anticipate that the continuous evolution of CANDY will inspire ongoing
improvements and adaptations in the field, addressing both current and
emerging challenges in dynamic data handling.

## References

  * [1] The number of tweets per day in 2022 , https://www.dsayce.com/category/social-media/, 2022.  Last Accessed: 2023-12-05.
  * [2] War thunder wiki , https://wiki.warthunder.com/, 2024.  Last Accessed: 2024-04-05.
  * [3] C. Aguerrebere, M. Hildebrand, I. S. Bhati, T. Willke, and M. Tepper.  Locally-adaptive quantization for streaming vector search.  arXiv preprint arXiv:2402.02044, 2024.
  * [4] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, R. Vijayakumar, and P. Whiting.  Scheduling in a queuing system with asynchronously varying service rates.  Probability in the Engineering and Informational Sciences, 18(2):191–217, 2004.
  * [5] V. Arun and H. Balakrishnan.  Copa: Practical $\\{$Delay-Based$\\}$ congestion control for the internet.  In 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18), pages 329–342, 2018.
  * [6] D. Baranchuk, D. Persiyanov, A. Sinitsin, and A. Babenko.  Learning to route in similarity graphs.  In International Conference on Machine Learning, pages 475–484. PMLR, 2019.
  * [7] A. Cidon, R. Escriva, S. Katti, M. Rosenblum, and E. G. Sirer.  Tiered replication: A cost-effective alternative to full cluster geo-replication.  In 2015 USENIX Annual Technical Conference (USENIX ATC 15), pages 31–43, 2015.
  * [8] A. Dong and B. Bhanu.  Concept learning and transplantation for dynamic image databases.  In 2003 International Conference on Multimedia and Expo. ICME’03. Proceedings (Cat. No. 03TH8698), volume 1, pages I–765. IEEE, 2003.
  * [9] W. Dong, C. Moses, and K. Li.  Efficient k-nearest neighbor graph construction for generic similarity measures.  In Proceedings of the 20th international conference on World wide web, pages 577–586, 2011.
  * [10] H. J. Fowler and W. E. Leland.  Local area network characteristics, with implications for broadband network congestion management.  IEEE Journal on Selected Areas in Communications, 9(7):1139–1149, 1991.
  * [11] C. Fu, C. Xiang, C. Wang, and D. Cai.  Fast approximate nearest neighbor search with the navigating spreading-out graph.  Proceedings of the VLDB Endowment, 12(5):461–474, 2019.
  * [12] J. Gao and C. Long.  High-dimensional approximate nearest neighbor search: with reliable and efficient distance comparison operations.  Proceedings of the ACM on Management of Data, 1(2):1–27, 2023.
  * [13] A. Gionis, P. Indyk, and R. Motwani.  Similarity search in high dimensions via hashing.  In VLDB, volume 99, pages 518–529, 1999.
  * [14] A. Héliou, P. Mertikopoulos, and Z. Zhou.  Gradient-free online learning in continuous games with delayed rewards.  In International conference on machine learning, pages 4172–4181. PMLR, 2020.
  * [15] Y. Huang, Y. Cheng, A. Bapna, O. Firat, D. Chen, M. Chen, H. Lee, J. Ngiam, Q. V. Le, Y. Wu, et al.  Gpipe: Efficient training of giant neural networks using pipeline parallelism.  Advances in neural information processing systems, 32, 2019.
  * [16] P. Indyk and R. Motwani.  Approximate nearest neighbors: towards removing the curse of dimensionality.  In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604–613. ACM, 1998.
  * [17] H. Jegou, M. Douze, and C. Schmid.  Product quantization for nearest neighbor search.  IEEE transactions on pattern analysis and machine intelligence, 33(1):117–128, 2010.
  * [18] W. Jiang, M. Zeller, R. Waleffe, T. Hoefler, and G. Alonso.  Chameleon: a heterogeneous and disaggregated accelerator system for retrieval-augmented language models.  arXiv preprint arXiv:2310.09949, 2023.
  * [19] V. Karpukhin, B. Oğuz, S. Min, P. Lewis, L. Wu, S. Edunov, D. Chen, and W.-t. Yih.  Dense passage retrieval for open-domain question answering.  arXiv preprint arXiv:2004.04906, 2020.
  * [20] P. Lewis, E. Perez, A. Piktus, F. Petroni, V. Karpukhin, N. Goyal, H. Küttler, M. Lewis, W.-t. Yih, T. Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  Advances in Neural Information Processing Systems, 33:9459–9474, 2020.
  * [21] M. Li, Y.-G. Wang, P. Zhang, H. Wang, L. Fan, E. Li, and W. Wang.  Deep learning for approximate nearest neighbour search: A survey and future directions.  IEEE Transactions on Knowledge and Data Engineering, 2022.
  * [22] W. Li, C. Feng, D. Lian, Y. Xie, H. Liu, Y. Ge, and E. Chen.  Learning balanced tree indexes for large-scale vector retrieval.  In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1353–1362, 2023.
  * [23] W. Li, Y. Zhang, Y. Sun, W. Wang, M. Li, W. Zhang, and X. Lin.  Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement.  IEEE Transactions on Knowledge and Data Engineering, 32(8):1475–1488, 2019.
  * [24] E. Loper and S. Bird.  Nltk: The natural language toolkit.  arXiv preprint cs/0205028, 2002.
  * [25] X. Luo, H.-H. Chen, and Q. Guo.  Semantic communications: Overview, open issues, and future research directions.  IEEE Wireless Communications, 29(1):210–219, 2022.
  * [26] Y. Lyu, Z. Li, S. Niu, F. Xiong, B. Tang, W. Wang, H. Wu, H. Liu, T. Xu, and E. Chen.  Crud-rag: A comprehensive chinese benchmark for retrieval-augmented generation of large language models.  arXiv preprint arXiv:2401.17043, 2024.
  * [27] Y. Malkov, A. Ponomarenko, A. Logvinov, and V. Krylov.  Approximate nearest neighbor algorithm based on navigable small world graphs.  Information Systems, 45:61–68, 2014.
  * [28] Y. A. Malkov and D. A. Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  In IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2018.
  * [29] C. D. Manning, P. Raghavan, and H. Schütze.  Introduction to information retrieval.  2008\.
  * [30] P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M. I. Jordan, et al.  Ray: A distributed framework for emerging $\\{$AI$\\}$ applications.  In 13th USENIX symposium on operating systems design and implementation (OSDI 18), pages 561–577, 2018.
  * [31] M. Muja and D. G. Lowe.  Scalable nearest neighbor algorithms for high dimensional data.  IEEE transactions on pattern analysis and machine intelligence, 36(11):2227–2240, 2014.
  * [32] NA.  Pytorch homepage, https://pytorch.org/, 2023.
  * [33] A. Singh, S. J. Subramanya, R. Krishnaswamy, and H. V. Simhadri.  Freshdiskann: A fast and accurate graph-based ann index for streaming similarity search.  arXiv preprint arXiv:2105.09613, 2021.
  * [34] N. Sundaram, A. Turmukhametova, N. Satish, T. Mostak, P. Indyk, S. Madden, and P. Dubey.  Streaming similarity search over one billion tweets using parallel locality-sensitive hashing.  Proceedings of the VLDB Endowment, 6(14):1930–1941, 2013.
  * [35] J. Wang, X. Yi, R. Guo, H. Jin, P. Xu, S. Li, X. Wang, X. Guo, C. Li, X. Xu, et al.  Milvus: A purpose-built vector data management system.  In Proceedings of the 2021 International Conference on Management of Data, pages 2614–2627, 2021.
  * [36] M. Wang, X. Xu, Q. Yue, and Y. Wang.  A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search.  Proceedings of the VLDB Endowment, 14(11):1964–1978, 2021.
  * [37] R. Weber, H.-J. Schek, and S. Blott.  A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces.  VLDB, 98:194–205, 1998.
  * [38] Y. Weiss, A. Torralba, and R. Fergus.  Spectral hashing.  In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008.
  * [39] D. Xu, I. W. Tsang, and Y. Zhang.  Online product quantization.  IEEE Transactions on Knowledge and Data Engineering, 30(11):2185–2198, 2018.
  * [40] B. Yuan, Y. He, J. Davis, T. Zhang, T. Dao, B. Chen, P. S. Liang, C. Re, and C. Zhang.  Decentralized training of foundation models in heterogeneous environments.  Advances in Neural Information Processing Systems, 35:25464–25477, 2022.
  * [41] X. Zeng, S. Zhang, H. Zhong, H. Zhang, M. Lu, Z. Zheng, and Y. Chen.  Pecj: Stream window join on disorder data streams with proactive error compensation.  Proceedings of the ACM on Management of Data, 2(1):1–24, 2024.
  * [42] H. Zhang, X. Zeng, S. Zhang, X. Liu, M. Lu, and Z. Zheng.  Scalable online interval join on modern multicore processors in openmldb.  In 2023 IEEE 39th International Conference on Data Engineering (ICDE), pages 3031–3042. IEEE, 2023.
  * [43] S. Zhang, Y. Mao, J. He, P. M. Grulich, S. Zeuch, B. He, R. T. Ma, and V. Markl.  Parallelizing intra-window join on multicores: An experimental study.  In Proceedings of the 2021 International Conference on Management of Data, pages 2089–2101, 2021.
  * [44] X. Zhao, Y. Tian, K. Huang, B. Zheng, and X. Zhou.  Towards efficient index construction and approximate nearest neighbor search in high-dimensional spaces.  Proceedings of the VLDB Endowment, 16(8):1979–1991, 2023.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes] In Section 4.

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]
It’s hard for us to consider the negative social impacts of AKNN, which is not
an application but a fundamental data science operator.

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [N/A]

    2. (b)

Did you include complete proofs of all theoretical results? [N/A]

  3. 3.

If you ran experiments (e.g. for benchmarks)…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]
At https://github.com/intellistream/candy.

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A] Model training is not within our major scope, but
we mentioned the details in our Appendix A.4 when machine learning is
involved.

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [No] The result in our running is stable multiple
times.

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Single-
thread, CPU only (Section 4).

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [No] Some of them like Glove are
just shipped under Dropbox links from creators, we included the license of the
rest in our code base (i.e., DPR and Random).

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes] WTE dataset in Appendix A.1.

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A] The data is a free Wiki and public resource.

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [No] While there is no
personally identifiable information included, it is challenging to ensure that
every term, such as aircraft nicknames, used in generating embeddings, is not
potentially offensive to someone.

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Appendix

###  A.1 Supplementary Details of CANDY Benchmark

This section provides supplementary details of the CANDY, including a
comprehensive overview of datasets, implementation specifics, and deployment
considerations.

Real-world | Name | Description | Dimension
---|---|---|---
Glove [23] | Text embedding | $100$
SIFT [23] | Image | $128$
Msong [23] | Audio | $4208$
Sun [23] | Image | $512$
DPR [3] | Text embedding | $768$
Trevi [23] | Image | $4096$
Synthetic |  Random [32] | i.i.d values | Adjustable
WTE [3, 2, 24] | Text embedding | $768$

Table 5: Datasets Summary.

#### More Details about Datasets

Table 5 summarizes the datasets. The DPR dataset was reconstructed using the
source code and corpus provided by Aguerrebere et al. [3], while the Glove,
SIFT, Msong, Sun, and Trevi datasets were obtained from Li et al. [23]. Each
real-world dataset is normalized using the _torch::norm_ function from
LibTorch [32] to ensure values range between -1 and 1. The Random dataset is
generated by the _torch::random_ function, producing a sequence of independent
and identically distributed (i.i.d.) uniform values between $0$ and $1$. This
dataset allows for configurable dimensions and volumes of vectors,
facilitating studies on dimensional scalability. In our experiments, we use
DPR if not otherwise specified. By default, we initially loaded AKNN with 50K
rows of vector in the offline stage. Afterwards, we enter the dynamic
ingestion phase by feeding AKNN with 50K new data (by default 4K rows/second),
and let the micro-batches sized $4K$.

The WTE dataset simulates text embedding processes similar to DPR but uses
synthetically generated text sentences. Each sentence comprises a subject,
predicate, and object, with both subject and object as nouns, and predicates
as random verbs from NLTK [24], ensuring no biased distribution. Controlled
data distribution shifts are introduced by varying the noun categories, for
instance, comparing nouns from USSR land vehicles against USA aircrafts from
Warthunder [2]. The embedding models used are static, without fine-tuning, set
to produce 768-dimensional vectors for 100K rows. Additionally, we manipulate
the occurrence position and intensity of distribution shifts in WTE. For
occurrence position, we adjust where vector embeddings transition from USA
aircraft nouns to USSR land vehicle nouns, with word contamination set to a
probability of 1 thereafter. To vary the shift intensity, we construct
sentences using USA aircraft nouns, randomly replace the subject noun with
“T-34-85,” and generate embeddings from these contaminated sentences. This
models real-world scenarios of emerging topics, with the “T-34-85”
representing a sudden shift in focus. The contamination probability is
adjustable to simulate varying intensities of this shift.

#### More Implementation Details

We have standardized the API access for all AKNN algorithms within CANDY to
include initialization processes, offline data loading, data ingestion, and
vector search, ensuring full compatibility with LibTorch and PyTorch [32],
popular tools in the data science community, across both C++ and Python. This
unified approach extends through our C++ codebase, utilizing static
compilation and interfaces based on _torch::Tensor_ to maintain consistency
and compatibility across experiments. Our implementation adheres to the IEEE
754 32-bit floating-point (FP32) format for vector elements and leverages
_torch::Tensor_ for vector representation, thereby aligning with LibTorch and
PyTorch without requiring extra conversions. All code and scripts are publicly
available at https://github.com/intellistream/candy, with additional
documentation provided in our codebase.

#### Parallel Hardware Considerations

Our experiments primarily utilized a Silver 4310 processor. We adapted
approximate k-nearest neighbor (AKNN) algorithms for parallel and distributed
computing, employing a straightforward sharding approach as outlined in Wang
et al.[35] and Moritz et al.[30]. However, this embarrassingly parallel
approach did not yield novel insights due to its inherent shared-nothing
architecture. We also refrained from implementing algorithm-specific
parallelization techniques, such as concurrent vertex writing in Hnsw [33, 3],
owing to the complexity of ensuring fairness in such configurations.
Therefore, our evaluation emphasizes single-threaded performance to ensure
consistency across tests.

###  A.2 More Related Work Discussion

#### More Discussions on Ranging-based AKNN

Locality Sensitive Hashing (Lsh [13]), one of the earliest ranging-based
AKNNs, hashes similar vectors into the same bucket to form ranges, though it
often faces criticism for its suboptimal trade-off between retrieval
efficiency and accuracy. Subsequent ranging-based AKNN methods have sought to
improve this by employing more sophisticated techniques like product
quantization (Pq [17]) and space partitioning (Flann [31]), which consider the
distribution of data collection $S$. Enhancements such as hierarchical range
layouts in Ivfpq [17], which uses two tiers of quantizers to refine Pq,
further boost retrieval efficiency. Despite their streamlined workflow for
data retrieval and ingestion, ranging-based AKNNs often struggle with
accurately determining ranges, which can misplace distant vectors in the same
range or similar vectors in separate ranges. Most rely on the assumption that
$S$’s distribution is known and static, except for onlinePQ, which
incrementally updates its cluster centroids to adapt to distribution shifts in
newly ingested data [39].

#### More Discussions on Navigation-based AKNN

Navigation-based AKNN employs various strategies to manage the navigation path
and decide when to halt the expansion of candidate neighbors. For instance,
Nsw [27] uses the Delaunay Graph strategy, while Nndecent [9] relies on the
K-Nearest Neighbor Graph. Both Dpg [23] and Nsg [11] utilize the K-Nearest
Neighbor Graph and Relative Neighborhood Graph approaches, with Nsg enhancing
Dpg ’s retrieval efficiency through different vertex assignment techniques.
Additionally, hierarchical designs similar to those in ranging-based AKNN are
also used in navigation-based methods. For example, Hnsw [28] builds multiple
layers of Nsw, significantly improving retrieval efficiency by avoiding the
flat structure limitations. Furthermore, the graph maintenance can also be
optimized by using hashing, as recently proposed by Lshapg [44]. Navigation-
based AKNN effectively overcomes the challenges of imprecise range
determination found in ranging-based methods, achieving higher retrieval
accuracy and efficiency. However, modifying navigation paths within a proxy
graph is a complex, iterative process, often requiring adjustments among
neighboring vectors.

###  A.3 Supplementary Experimental Insights

This section presents additional insights gained from using CANDY.
Specifically, we highlight significant issues such as the queuing of
uningested data and re-examine the well-documented “curse of dimension” [23]
in the context of dynamic data ingestion. Additional findings concerning data
sources and data volumes are also discussed.

Algorithms | Recall@10 | Query Latency ($\times 1000ms$)
---|---|---
Glove | SIFT | Msong | Sun | DPR | Trevi | Glove | SIFT | Msong | Sun | DPR | Trevi
Baseline | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.43 | 0.44 | 0.59 | 0.70 | 0.74 | 2.54
Ranging-based | Lsh | 0.00 | 0.01 | 0.00 | 0.00 | 0.00 | 0.07 | 0.21 | 0.23 | 0.23 | 0.42 | 0.20 | 12.33
Flann | 0.01 | 0.01 | 0.00 | 0.09 | 0.02 | 0.13 | 0.02 | 0.02 | 0.02 | 0.02 | 0.05 | 0.08
Pq | 0.12 | 0.30 | 0.75 | 0.53 | 0.10 | 0.53 | 2.44 | 3.68 | 8.83 | 373.37 | 5.63 | 22.14
Ivfpq | 0.04 | 0.23 | 0.02 | 0.33 | 0.15 | 0.42 | 4.11 | 6.19 | 18.94 | 5.66 | 16.97 | 22.22
onlinePQ | 0.12 | 0.31 | 0.82 | 0.52 | 0.10 | 0.52 | 2.53 | 1.21 | 16.86 | 399.04 | 29.81 | 162.16
Navigation-based | Hnsw | 0.60 | 0.90 | 1.00 | 0.99 | 0.80 | N.A. | 733.55 | 178.88 | 560.32 | 4411.18 | 1008.13 | N.A.
Nsw | 0.14 | 0.55 | 0.34 | 0.78 | 0.52 | N.A. | 1722.13 | 230.68 | 2659.95 | 1389.90 | 1349.35 | N.A.
Nsg | N.A. | 0.01 | 0.00 | 0.04 | 0.01 | 0.03 | N.A. | 0.02 | 0.03 | 0.02 | 0.06 | 0.11
Nndecent | 0.01 | 0.12 | 0.00 | 0.23 | 0.17 | 0.46 | 267.26 | 591.39 | 390.37 | 340.39 | 556.66 | 734.74
Dpg | 0.08 | 0.33 | 0.06 | 0.30 | 0.31 | 0.48 | 7639.13 | 1134.88 | 5009.27 | 906.83 | 1335.47 | 4308.02
Lshapg | 0.07 | 0.10 | 0.59 | 0.24 | 0.10 | 0.24 | 31.16 | 24.67 | 41.81 | 53.84 | 52.31 | 180.05

Table 6: Comparing AKNN algorithms with dynamic data ingestion when queuing
uningested data. N.A. means that the evaluation of certain algorithms and
certain datasets exceeds 4h wall time, and therefore unable to get further
results.

Algorithms | Propotion of PWL (%) | PWL ($\times 1000ms$) | VSL ($\times 1000ms$)
---|---|---|---
Msong | DPR | Trevi | Msong | DPR | Trevi | Msong | DPR | Trevi
Baseline | 73.04 | 0.00 | 60.86 | 0.44 | 0.50 | 1.50 | 0.15 | 0.24 | 1.03
Ranging-based | Lsh | 74.71 | 88.03 | 1.12 | 0.17 | 0.18 | 0.13 | 0.06 | 0.02 | 12.20
Flann | 98.90 | 99.86 | 99.24 | 1.69 | 37.89 | 9.95 | 1.71 | 37.94 | 10.02
Pq | 97.12 | 95.36 | 98.13 | 8.58 | 5.38 | 21.87 | 0.25 | 0.25 | 0.26
Ivfpq | 97.75 | 96.05 | 91.11 | 18.68 | 16.64 | 20.24 | 0.26 | 0.33 | 1.99
onlinePQ | 98.47 | 99.16 | 99.85 | 16.61 | 29.57 | 161.91 | 0.25 | 0.25 | 0.25
Navigation-based | Hnsw | 99.99 | 99.99 | N.A. | 560.26 | 1008.00 | N.A. | 0.05 | 0.13 | N.A.
Nsw | 100.00 | 99.98 | N.A. | 2659.85 | 1349.03 | N.A. | 0.09 | 0.32 | N.A.
Nsg | 99.99 | 99.99 | 99.99 | 388.36 | 465.32 | 929.59 | 388.39 | 465.39 | 929.71
Nndecent | 99.81 | 99.86 | 99.85 | 389.62 | 555.88 | 733.62 | 0.76 | 0.78 | 1.13
Dpg | 99.96 | 99.91 | 99.92 | 5007.04 | 1334.21 | 4304.74 | 2.23 | 1.26 | 3.27
Lshapg | 99.39 | 98.94 | 99.43 | 41.55 | 51.75 | 179.02 | 0.25 | 0.56 | 1.03

Table 7: Break down the query latency into pending write latency and vector
search latency when queuing uningested data. “PWL” is short for pending
writing latency, and “VSL” is short for vector search latency. N.A. means that
the evaluation of certain algorithms and certain datasets exceeds 4h wall
time, and therefore unable to get further results.

#### It’s not Practically Useful to Queue Uningested Data Due to Large Extra
Latency

Contrary to the default drop-on-congestion approach, we experimented with
storing congested data in an in-memory queue, allowing AKNN to process all
incoming data eventually. However, our tests show that queuing decreases
ingestion efficiency, contradicting its assumed practicality. In cross-
validation tests reported in Table 6 and 7, we maintained all settings
identical to those in Tables 2 and 3, except that the data source was paused
to ensure complete data ingestion. Notably, while avoiding data dropping does
increase recall—for example, Hnsw ’s recall improved from 0.61 to 1.00 in
processing the Msong dataset—this method also significantly increases vector
search latency and overall query processing time. For instance, the vector
search latency for onlinePQ in the DPR dataset decreased dramatically from
3.43s to 0.25s due to fewer traversals through distant vectors when the
complete dataset is ingested. However, the total latency for queries, such as
those handled by Hnsw for the DPR dataset, increased from approximately 691s
to 1008s. This increase is due to intrinsic delays in updating AKNN compared
to the data source, with added costs from memory operations and cache misses,
which significantly enlarge end-to-end query latency.

#### The “Curse of Dimension” is Compounded in Dynamic Ingestion

Scalability concerning vector dimensions remains a pivotal issue for AKNN, as
underscored in previous studies [23]. In our exploration with the Random
dataset, where dimensions ranged from 64 to 4096, we observed notable
insights. Consistent with static data evaluations [23], navigation-based AKNNs
such as Hnsw generally surpass ranging-based AKNNs like Ivfpq in recall, due
to their efficient preservation of data relationships and minimal assumptions,
albeit at a cost of increased memory usage leading to out-of-memory issues.
Contrary to established expectations [23, 28], apart from Lsh, all tested
AKNNs displayed a greater susceptibility to the “curse of dimension,” with
pronounced increases in query latency as dimensions expanded. This contradicts
the belief that AKNNs inherently minimize performance degradation with
increased dimensions [17, 28], revealing an over-optimization in vector search
capabilities at the expense of ingestion efficiency, and highlights a critical
area for improvement.

(a) Query Recall

(b) Query Latency.

Figure 6: Revisit the “curse of dimension” under online ingestion. Hnsw and
Nsw run out of memory under 4096-D case.

(a) Query Recall

(b) Query Latency.

Figure 7: Tuning event rate from $20$ to $5000$, the unit of event rate is
$rows/s$.

#### Impact of Increased Event Rates on AKNN Performance

We examined the effects of varying event rates on AKNN performance using the
DPR dataset, adjusting the data rate in CANDY from 20 to 5000 rows per second.
As shown in Figure 7, AKNN systems generally perform worse as the event rate
surpasses their ingestion capacity—for instance, about 20 rows per second for
Hnsw —resulting in increased query latency and decreased recall due to data
loss. Although Lsh manages to keep pace with an event rate of 5000 rows/s, its
recall remains too low for practical use. We noted that navigation-based AKNNs
like Hnsw, Nsw, and Nsg exhibit much greater fluctuations in query latency—up
to ten times higher—compared to ranging-based AKNNs such as Lsh or Ivfpq. This
instability stems from the iterative scanning and comparison requirements
within their proximity graphs, making them more susceptible to mismatches
between data arrival and ingestion rates.

#### Impact of Data Volume on AKNN Performance Under Online Ingestion

Data scalability related to vector volume remains a crucial challenge for
Approximate AKNN, as noted in prior research [23]. To assess this in an online
ingestion context, we used the Random dataset with vector volumes ranging from
60K to 5M vectors, while the first 50K vectors were pre-loaded during the
offline phase. Figure 8 illustrates how these adjustments affect query recall
and latency. Our findings reveal two main points: First, consistent with prior
studies [23, 39], there is a general increase in query latency as vector
volume grows, with onlinePQ showing a relatively slower rate of increase
compared to Baseline, suggesting some level of efficiency in managing larger
data volumes (Figure 8(b)).

Second, this dynamic ingestion scenario complicates the accuracy outcomes for
AKNN. Although Hnsw typically shows superior accuracy, its performance drops
below Lsh when handling more than 500K vectors (Figure 8(a)). This decline
contradicts previous static evaluations where Hnsw maintained high recall
regardless of data volume [28]. The observed decrease in accuracy is due to
inefficient data ingestion and the resultant data dropping, which impedes the
algorithm’s ability to maintain accurate vector searches. Similarly, Baseline
begins to lose accuracy at a vector volume of 5M, highlighting the operational
costs associated with reallocating and copying large data volumes during
ingestion, even when managed in-memory.

(a) Query Recall

(b) Query Latency.

Figure 8: Tuning the vector volume from $60K\sim 5M$. Flann runs out of memory
when the volume reaches $5M$.

###  A.4 Additional Setup Details for Machine Learning and Distance
Computation Optimization

For machine learning optimization, we employ a neural network (NN) to replace
the traditional hash function in Lsh, enhancing its data organization
capability. The NN, a simple multilayer perceptron (MLP), is pre-trained
offline. It consists of a linear encoding layer with a _tanh_ activation
function, followed by a decoding layer, tailored to approximate the spectral
hashing loss function [38]. The output undergoes an adjustment by subtracting
a trainable bias matrix for refined hashing. This implementation focuses on
computational simplicity and generalization to typical AKNN tasks.

For distance compute optimization, we implement distance optimization
strategies for Hnsw using L2 distance instead of the default inner product to
align with specific optimization techniques [12]. The optimizations include:
1) Locally-Adaptive Vector Quantization (LVQ) [3], which uses a global mean to
scale vectors and local extremes for quantization, thus allowing for reduced
computation costs in distance calculations; 2) ADSampling [12], which
introduces a randomized transformation of input and query vectors, with
incremental distance evaluations against a pre-defined threshold to
potentially cut off unnecessary computations, thus enhancing processing speed
and efficiency.


# A Boundary Approximation Algorithm for Distributed Sensor Networks

Michael I. Ham  Marko A. Rodriguez  Theoretical Division - Center for
Nonlinear Studies, Los Alamos National Laboratory, Los Alamos, New Mexico
87545

###### Abstract

We present an algorithm for boundary approximation in locally-linked sensor
networks that communicate with a remote monitoring station. Delaunay
triangulations and Voronoi diagrams are used to generate a sensor
communication network and define boundary segments between sensors,
respectively. The proposed algorithm reduces remote station communication by
approximating boundaries via a decentralized computation executed within the
sensor network. Moreover, the algorithm identifies boundaries based on
differences between neighboring sensor readings, and not absolute sensor
values. An analysis of the bandwidth consumption of the algorithm is presented
and compared to two naive approaches. The proposed algorithm reduces the
amount of remote communication (compared to the naive approaches) and becomes
increasingly useful in networks with more nodes.

††preprint: LA-UR-09-00111

##  I Introduction

Sensor networks consist of a set of sensor devices that communicate with each
other through a wired or wireless communication network. Such systems often
communicate with a remote station and are a promising technology for remotely
detecting physical phenomena such as forest fires, chemical leaks, or
radioactive clouds. For many applications, it is necessary that the network
not only identify a phenomenon, but also determine the boundary of the
detected phenomenon. For example, by establishing the boundary of a forest
fire, a sensor network can help fire fighters determine where to concentrate
their efforts.

Adding more sensors to a network increases the accuracy of any boundary
approximation algorithm, but consequently, increases the amount of data
generated. Therefore, if all data is processed at the remote station, the
required bandwidth is proportional to the size of the network. On the other
hand, if only the nodes that sense the phenomenon report back, the required
bandwidth is proportional to the size of the phenomenon. As an alternative to
both of these naive approaches, we present a decentralized algorithm for
boundary identification that limits remote station communication by
determining the boundary segments of a phenomenon via a distributed
computation that is carried out within the sensor network. Moreover, only
sensors that identify a boundary ultimately communicate with the remote
station. Therefore, the amount of remote communication is proportional to the
size of the phenomenon’s boundary.

##  II Two Naive Boundary Approximation Algorithms

A naive solution to boundary approximation would be for each sensor to report
its internal state to the remote station. Once the state of each sensor
reaches the remote station, the station calculates the boundary using either a
centralized version of the proposed method (to follow) or any other known
centralized algorithm. Assuming $n$ nodes in the sensor network and each
sensor has a cost of $\beta$ for a long-range transmission, the cost of this
approach is $n\beta$. However, a complication with this approach is that the
remote station must have the capacity to receive information from each node
simultaneously in order to ensure an accurate snapshot of the phenomenon’s
location. Regardless, as the size of network increases, this approach becomes
prohibitive since the cost scales with the number of sensors.

A second naive solution would be for only those sensors that detect the
phenomenon to report back to the remote station. If $m$ is the number of nodes
sensing a phenomenon, where $m\leq n$, then $m\beta$ would be cost of this
algorithm. Using this method, remote communication scales with the size of the
phenomenon, not the size of the network. A simple real-world example
demonstrates a potential fault with this approach for certain phenomena.
Imagine a sensor network whose function is to sense a gray-scale environment.
Given a constant light source, a sensation threshold can be determined. In
such cases, only those sensors that sense a high enough gray-scale value would
report to the remote station. However, once the light source is reduced beyond
the preset sensation threshold, the phenomenon is no longer detected even
though there exists a relative difference in the readings of the sensors at
the boundary. Using the algorithm presented next, a relative analysis
determines the boundary regardless of the strength of the light source
(assuming there exists more light than absolute dark). Sensors use local
communication to detect a boundary by comparing neighboring measurements and
only sensors that identify a boundary communicate with the remote station.
Finally, the number of sensors reporting scales with the size of the
phenomenon’s boundary. In many cases, the area of a phenomenon is likely to be
significantly larger than the boundary.

##  III The Proposed Boundary Approximation Algorithm

Given a sensor network with $n$ nodes, a Delaunay triangulation is used to
determine the neighbors of each node in the network delaunay:lee1980 . Next, a
Voronoi diagram is generated to determine boundary segments between
neighboring sensors. Such diagrams create cells with boundaries (segments),
where all points on the cell boundary are equidistant between the two
neighboring sensor nodes voronoi:aurenhammer1991 . Figure 1 presents a
visualization of a Delaunay triangulation (Figure 1a) and Voronoi diagram
(Figure 1b) for $100$ randomly distributed nodes within a 2D space. Because
there exists no distributed algorithm for calculating a Delaunay
triangularization and a Voronoi diagram cover:li2003 , the sensor network’s
remote station can be used to calculate these. This one time calculation
occurs only after sensors have been distributed and assumes that the remote
station knows the exact location of each sensor.

Figure 1:  a. A Delaunay triangulation and b. a Voronoi diagram for 100
randomly distributed sensors. Sensors $i$ and $j$ are identified as well as
the $(i,j)$ Voronoi cell boundary that is equidistant between $i$ and $j$.

Assume that a given sensor $i$ takes a measurement $\psi_{i}\in[0,1]$. In
order to accomplish a local, distributed calculation of a phenomenon’s
boundary, $i$ must communicate with each of its neighbors and compare its
measurement with the measurements taken by those neighbors. If a particular
neighbor $j$ of $i$ has a $\psi_{j}$ that is significantly different than
$\psi_{i}$, then $i$ can assume that the phenomenon’s boundary exists
somewhere between itself and $j$. This threshold of difference is defined by
$\theta\in[0,1]$ and a boundary exists when $\psi_{i}-\psi_{j}>\theta$. Since
sensors have spatial gaps between them, the location of the boundary cannot be
known exactly. The best approximation of the phenomenon’s boundary is
determined to be the line directly equidistant from $i$ and $j$. Conveniently,
this line is the segment $(i,j)$ as defined by the Voronoi diagram. Therefore,
once $(i,j)$ is determined to be a boundary segment, only this information
needs to be transmitted to the remote station. Thus, only those sensors at the
boundary of the phenomenon are communicating with the remote station.
Moreover, the aggregate of all their reports is the approximated boundary.

Figure 2 presents two simulated phenomenon: one with a linear boundary and the
other with a circular boundary. Each phenomena exist within a $100$ node
sensor network. Table 1 presents the cost of each boundary detection approach
for both phenomena, where $\epsilon$ denotes the relatively low cost of all
inter-node communication comm:wierelthier2000 . It should be noted that for
certain types of networks, especially radio wireless networks, the cost of
local communication can be orders of magnitude less than long-range, remote
communication. It is in these situations where the proposed algorithms is most
efficient.

Figure 2:  A representation of the boundary approximated by the proposed algorithm for phenomena with a. linear and b. circular boundaries. Gray-scale shading denotes the phenomena. The boundary of the phenomena is the black line and the approximated boundary is the dashed line. The approximated boundary is always a collection of Voronoi cell segments. boundary |  1${}^{\text{st}}$ naive |  2${}^{\text{nd}}$ naive | proposed
---|---|---|---
linear | $100\beta$ | $80\beta$ | $11\beta+\epsilon$
circular | $100\beta$ | $38\beta$ | $24\beta+\epsilon$
Table 1: The cost of each approach for simulated phenomena with linear and
circular boundaries (see Figure 2). $\beta$ denotes the cost for remote
communication and $\epsilon$ is the total cost for inter-network
communication.

##  IV Monte Carlo Simulation

Monte Carlo simulations provide a means to test a system with many degrees of
freedom, where an exhaustive parameter sweep is considered intractable
metropolis_1949 . We utilize a Monte Carlo simulation of sensor networks
containing $3$, $4$, $5$, $10$, $25$, $100$, $200$, $500$, and $1000$ nodes.
For each population of nodes, one hundred different 2D space configurations
are created within a fixed area. In each of the one hundred configurations, we
activate a random set of nodes. The number of activated nodes is sequentially
increased from $1$ to $n$. This random selection of nodes is done 100 times.
For each resulting pattern, we calculate the number of sensors that would
report back to the central station using the various boundary detection
algorithms previously described. Figure 3 presents the results for networks of
$10$, $100$, and $1000$ nodes using the first naive approach (top horizontal
line), the second naive approach (black diagonal line), and our proposed
approach (gray cloud). Finally, Table 2 demonstrates for all networks tested,
the maximum number of nodes reporting to the remote station. The results of
Table 2 demonstrate that the proposed algorithm becomes more efficient as more
nodes are added to the network. It should be noted, that for both naive
approaches, the maximum number of reporting nodes is 100%.

Figure 3:  A Monte Carlo simulation of the number of nodes (as a percent of the whole population) observing a phenomenon vs. the number (as a percent of the whole population) reporting back to the remote station in networks with $10$, $100$, and $1000$ nodes. For the proposed algorithm, as the number of nodes increases, the maximum number of nodes reporting to the remote station decreases. number of nodes | max reporting (%)
---|---
3 | 100
4 | 100
10 | 90
25 | 84
100 | 72
200 | 68
500 | 63.6
1000 | 61.5
Table 2: A Monte Carlo simulation identifies the maximum number of reporting
nodes for the proposed algorithm.

##  V Conclusions

Related work on boundary approximation in sensor networks relies mainly on
local communication and distributed computation edge:liao2003 ; local:chin2003
; image:deva2003 ; bound:nowak2003 . However, most boundary approximation
algorithms do not determine the boundary of the phenomenon, only the sensors
that lie at the boundary. By knowing which sensor’s lie at the boundary, the
remote station can then estimate the actual line defining the boundary of the
phenomenon. In contrast, the proposed algorithm computes the phenomenon’s
boundary internal to the network without reliance on the remote station. Local
communication is used to identify pairs of nodes with readings whose
difference is greater than $\theta$. One of the two nodes transmits the pair’s
Voronoi segment to the remote station. The aggregation of all these segments
is the approximated boundary of the phenomenon.

It should be noted that a boundary can never be determined exactly since
spatial gaps exist between sensors. Therefore, any calculation of the
phenomenon’s boundary is only an approximation. To reduce boundary location
uncertainty, more sensors can be added to the network. As sensor networks
increase in size, it is important to keep costs to a minimum. Costs can be
reduced by utilizing low bandwidth communication and energy efficient
processors with moderate clock speeds and small amounts of on-board memory.
The proposed algorithm helps achieve one of these objectives by reducing
remote station communication. The algorithm may prove useful in wireless
sensor networks where radio communication over long distances requires
significantly more energy than local communication comm:wierelthier2000 .

## Acknowledgements

We would like to thank Levi Larkey and Vadas Gintautas for their contributions
to this article. This research was funded by a U.S. Department of Education
GAANN Fellowship and an IC Postdoctoral Fellowship. Further support was
provided by the Los Alamos National Laboratory.

## References

  * (1) Franz Aurenhammer.  Voronoi diagrams - a survey of fundamental geometric data structure.  ACM Computing Surveys (CSUR), 23(3):345–405, 1991.
  * (2) Krishna Kant Chintalapudi and Ramesh Govindan.  Localized edge detection in sensor fields.  Ad-hoc Networks Journal, 2003.
  * (3) Divya Devaguptapu and Bhaskar Krishnamachari.  Applications of localized image processing techniques in wireless sensor networks.  In Edward M. Carapezza, editor, Unattended Ground Sensor Technologies and Applications V, volume 5090, pages 247–256. SPIE, 2003\.
  * (4) D.T. Lee and B.J. Schachter.  Two algorithms for constructing a delaunay triangulation.  International Journal of Computer and Information Sciences, 9(3):219–242, 1980.
  * (5) Xiang-Yang Li, Peng-Jun Wan, and Ophir Frieder.  Coverage in wireless ad hoc sensor networks.  IEEE Transactions on Computers, 52(6):753–763, 2003.
  * (6) Pei-Kai Liao, Min-Kuan Chang, and C.C. Jay Kuo.  Distributed edge detection with composite hypothesis test in wireless sensor networks.  In Proceedings of the Global Telecommunications Conference, pages 129–133. IEEE, 2004.
  * (7) N. Metropolis and S. Ulam.  The Monte Carlo method.  Journal of the American Statistical Association, 44:335–341, 1949\.
  * (8) Robert Nowak and Urbashi Mitra.  Boundary estimation in sensor networks: Theory and methods.  In Information Processing in Sensor Networks: Second Internationl Workshop IPSN, pages 80–95. Springer-Verlag, 2003.
  * (9) Jeffrey .E Wieselthier, Gam D. Nguyen, and Anthony Ephremides.  On the construction of energy-efficient broadcast and multicasttrees in wireless networks.  In INFOCOM ’2000: Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, pages 585–594, Washington, DC, USA, 2000. IEEE Computer Society.