Maintaining Structural Integrity through Physical Deletion

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 115 papers22 conceptsfrozen 2026-10-04

In high-performance data structures, deleting an item is often harder than adding one. To keep update speeds high, many systems use logical deletion: instead of removing a data point and restructuring the index, they simply mark it with a "tombstone" or "ghost" flag.

While this provides near-instant update latency, it creates a hidden debt. As Tomohiro Yamashita and Daichi Amagata argue in How Should We Evaluate Data Deletion in Graph-Based ANN Indexes?, these ghost nodes remain part of the topology. Search algorithms must still traverse them, leading to a linear degradation in throughput and a bloated memory footprint. Recent research focuses on moving beyond these markers toward efficient physical deletion—strategies that reclaim memory and maintain structural integrity without the massive overhead of a full rebuild.

The Problem of Structural Pollution

Whether in a concurrent stack, a spatial tree, or a vector index, the accumulation of logically deleted nodes leads to "structural pollution." In a quadtree, for instance, Wei Zhou and colleagues note in Quadboost: A Scalable Concurrent Quadtree that empty or logically removed nodes create unnecessarily long search paths, dragging down performance during high contention.

The challenge is that physical deletion is computationally expensive and risky in concurrent environments. In a lock-free hash table, for example, Barak A. Pearlmutter and Robert J. Kelly explain in Lock-Free Hopscotch Hashing that rebalancing a structure while other threads are actively traversing it is notoriously difficult. Without "true" physical deletion, however, probe chains grow longer and search efficiency inevitably decays.

Decoupling Intent from Adjustment

A recurring solution to this problem is decoupling. Instead of forcing a single atomic operation to handle both the logical removal and the physical cleanup, researchers separate them into two phases.

In A Wait-Free Stack, Seep Goel and Smruti R. Sarangi demonstrate this by decoupling the "pop" operation from the stack's top pointer. They use a lazy cleanup mechanism to prune deleted nodes, achieving high parallelism by ensuring that the structural "repair" doesn't block the primary data operations. Similarly, Haoxuan Xie and Siqiang Luo highlight in VectorMaton that hybrid indexing structures require robust garbage collection to prevent fragmentation from overwhelming the system's storage efficiency.

Preserving Navigability via Random Walks

The stakes for physical deletion are highest in graph-based Approximate Nearest Neighbor (ANN) search, like HNSW. If you simply delete a node and its edges, you risk fragmenting the graph, leaving some regions unreachable.

To solve this, Nina Mishra, Tal Wagner, and their team developed SPatch, detailed in Graph-based Nearest Neighbors with Dynamic Updates via Random Walks. SPatch treats the graph search as a random walk. When a node is removed, the algorithm uses random walk theory to mathematically determine which new edges should be added to preserve the graph's "navigability."

This approach offers a middle ground:

  1. Logical Deletion: Fast updates, but slow searches and high memory use.
  2. Full Rebuild: Perfect searches and memory, but extremely slow updates.
  3. SPatch (Physical Repair): Fast updates, fast searches, and low memory use by maintaining the mathematical properties of the graph during removal.

The Cost of Cleanliness

Physical deletion is not a free lunch. As Michael Mitzenmacher explores in A New Approach to Analyzing Robin Hood Hashing, schemes that avoid tombstones often require maintaining additional global state or metadata (like tracking the maximum displacement of keys).

The research direction across these papers suggests a shift in how we view data structure longevity. Rather than treating deletion as a secondary concern to be handled by occasional "rebuilds," modern approaches integrate structural repair into the lifecycle of the data structure itself. By decoupling the removal of data from the reclamation of space, these systems maintain high performance even under heavy, long-term update loads.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_maintaining_structural_integrity_through_a4740761,
  title = {Maintaining Structural Integrity through Physical Deletion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maintaining-structural-integrity-through-physical-deletion/rdr_a4740761872f49e9be5e0380a15584ff},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_maintaining_structural_integrity_through_a4740761_v1,
  title = {Maintaining Structural Integrity through Physical Deletion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/maintaining-structural-integrity-through-physical-deletion/rdr_a4740761872f49e9be5e0380a15584ff/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}