Skip to main content

ESS Logo Empty Space Search (ESS)

PyPI - Version PyPI - Python Version GitHub License GitHub Actions Workflow Status GitHub last commit

ESS is a high-performance Python library that implements the Empty Space Algorithm (ESA), a novel method for generating spatially diverse point distributions. It simulates electrostatic repulsive forces to "relax" new points into the empty spaces of a high-dimensional domain, making it ideal for sampling, coverage optimization, and exploratory data analysis.

Features

  • Empty Space Algorithm (ESA): Uses physics-inspired repulsive forces (Gaussian, Softened Inverse, etc.) to maximize the separation between points.
  • Toroidal Geometry (New in v0.4.0): The relaxation runs on the unit torus $[0, 1)^d$ under the toroidal L1 metric — opposite faces are identified, so there are no walls, no clipping, and no edge-clumping artifacts by construction.
  • Radius-Based Interactions: Supports physical range searches (interacting with all neighbors within a radius) alongside standard k-NN, with automatic L1-ball radius estimation for high-dimensional spaces.
  • Single Scalable Engine: Neighbour search is torann — exact brute force at small N, toroidal LSH above its threshold, chosen internally; per-epoch coordinate updates are native (no index rebuilds).
  • Robust Early Stopping: Convergence is detected on the force field itself (plateau of the largest net force, learning-rate-decoupled), typically stopping in tens of epochs instead of hundreds.
  • High-Dimensional Metrics: Includes robust coverage metrics (Maximin, Clark-Evans Index, Sparse Grid Coverage) optimized for dimensions > 32D.
  • Smart Initialization: Uses a vectorized "Best Candidate" sampling strategy to seed new batches in the most promising void regions.

Note: The library is designed to be compliant with modern Python 3.12+ standards.

Installation

The library can be installed directly from PyPI:

pip install EmptySpaceSearch

Alternatively, you can install the latest development version directly from GitHub:

pip install git+[https://github.com/mariolpantunes/ess.git](https://github.com/mariolpantunes/ess.git)

Requirements:

  • Python >= 3.10
  • numpy
  • torann

Usage

Basic Example

Generate 100 new points in a 2D space using the default settings (LHS Initialization + Auto-Radius + Repulsive Walls):

import numpy as np
import ess

# Define existing points (e.g., obstacles)
obstacles = np.array([[0.5, 0.5]]) 
bounds = np.array([[0, 1], [0, 1]])

# Generate 100 new points
# 'ess' returns the combined set (obstacles + new points)
result = ess.ess(obstacles, bounds, n=100, seed=42)

print(f"Total points: {len(result)}")

Advanced Usage with a Custom Index & LHS Sampler

A pre-configured torann.ToroidalNN (specific backend, LSH parameters) can be passed in, together with space-filling samplers and the physics-based radius mode:

import numpy as np
from ess import esa, ToroidalNN, LHCSampler

# 1000 existing points in 50 dimensions
dim = 50
obstacles = np.random.rand(1000, dim)
bounds = np.array([[0, 1]] * dim)

# Optional: explicit engine configuration (backend, thresholds, ...)
index = ToroidalNN(seed=42, backend="rust")

# Initialize Space-Filling Sampler (LHS)
lhs_sampler = LHCSampler(random_state=42)

# Run ESA (returns ONLY the new points)
# search_mode='radius' activates the dense physical interaction model
new_points = esa(
    obstacles, 
    bounds, 
    n=500, 
    index=index,
    init_sampler=lhs_sampler,  # Set custom LHS sampler
    search_mode='radius',      # Use radius instead of k-NN
    radius=None,               # None = Auto-compute based on density
    batch_size=100, 
    epochs=256
)

Algorithms

ESA (Empty Space Algorithm) treats existing points as fixed charged particles and new points as free moving charges.

  1. k-NN Mode: Points are repelled by their nearest neighbors. Good for maintaining local uniformity.
  2. Radius Mode (New): Points are repelled by all neighbors within a specific cutoff radius. This mimics real electrostatic fields and prevents "tunneling" in high-density regions.

Force Functions (all evaluated on the distance normalised by the interaction radius, so their parameters are dimension-free):

  • gaussian: Smooth, short-range repulsion. Default — best mean dispersion in the benchmark.
  • softened_inverse: Standard electrostatic repulsion (Coulomb-like).
  • linear: Simple linear drop-off (Hookean spring), hard cutoff at the radius.
  • cauchy: Heavy-tailed distribution for global separation.

Repulsion is local. Only the nearest few neighbours matter: further ones add an isotropic pressure that moves points without improving separation. The default k is therefore capped (ess.K_LOCAL, 5) rather than growing as 2d+1 — with a growing k, a 64-dimensional design has every point interacting with a quarter of the whole set, which collapses the one-dimensional marginals and leaves packing worse than random.

Measuring a design

Uniformity metrics do not survive high dimension equally well, so ess.utils offers the ones appropriate to each regime:

function what it measures rank designs with it?
wrap_around_discrepancy deviation from uniform over every wrap-around box, full dimension yes
projection_discrepancy the same, averaged over 1-D / 2-D coordinate projections; fixed scale in any ambient $d$ yes
expected_discrepancy the null both are divided by, so 1.0 = as uniform as random —
toroidal_separation the smallest toroidal $L_1$ gap in the set diagnostic only
euclidean_separation, calculate_grid_coverage non-wrapping separation, and grid occupancy provenance only

Rank designs with the two discrepancies. They measure deviation from uniformity and reference no point metric at all, so no choice of geometry can flatter an arm that happened to optimise it. Divide by expected_discrepancy(n, s) and the scale is fixed: 1.0 is as uniform as random, lower is better, and above 1.0 is worse than random — a real and observed failure mode, not a rounding artefact.

The separations are raw distances, so they are only meaningful inside one fixed geometry; ranking an $L_1$-optimised design against an $L_2$-optimised one with either asks which is better at the thing one of them optimised. calculate_grid_coverage saturates and inverts above $d \approx 8$ and cannot be built past $d \approx 20$.

Clark-Evans has been removed. It has meaning only divided by an expected nearest-neighbour distance, which makes it a statistic about a metric rather than about uniformity — so it cannot compare designs that optimised different geometries, which is most of the comparisons worth making. It was also blunt where it was valid: across a change under which 2-D projection discrepancy moved six-fold, it moved 1.4%, and it scored a design that is worse than random in its projections as 24% better than random.

Benchmark

examples/benchmark_dispersion.py runs the calibration behind the defaults — force-law selection, a tuning grid, and the main sweep over $d \in {2,\dots,64}$ with the number of points scaled to the dimension:

python examples/benchmark_dispersion.py --phase all --seeds 10

Documentation

This library is documented using Google-style docstrings.

You can access the full documentation online here.

To generate the documentation locally using pdoc:

pdoc --math -d google -o docs src/ess \
    --logo assets/ess_logo.svg \
    --favicon assets/ess_logo.svg

Authors

License

This project is licensed under the MIT License - see the LICENSE file for details.

Metadata

Release files for EmptySpaceSearch 0.4.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for EmptySpaceSearch 0.4.0
File Size Uploaded Provenance Actions
emptyspacesearch-0.4.0.tar.gz 51.4 kB Without provenance Details for emptyspacesearch-0.4.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for EmptySpaceSearch 0.4.0
File Interpreter ABI Platform Actions
emptyspacesearch-0.4.0-py3-none-any.whl Python 3 none any Details for emptyspacesearch-0.4.0-py3-none-any.whl

Total release size: 92.3 kB

Release files / emptyspacesearch-0.4.0.tar.gz

Download URL emptyspacesearch-0.4.0.tar.gz
Size 51.4 kB
Tags Source
SHA-256 checksum
How to use checksums
49728c7acbb48967487f4de6aa53a6ead7b7223c2a0b62d0fcd5f4a97ffaadb2
BLAKE2b-256 checksum
How to use checksums
962ced5ea28dbbe57e6b0c4d5323fbf7167c0018ce4afeec008d7c7a78dc0538
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.14

Release files / emptyspacesearch-0.4.0-py3-none-any.whl

Download URL emptyspacesearch-0.4.0-py3-none-any.whl
Size 40.9 kB
Tags Python 3
SHA-256 checksum
How to use checksums
37ac9c82d082330b2a403f0beba8d207fb4abc622fee96bdc7d3667ad9e80bd8
BLAKE2b-256 checksum
How to use checksums
ba92e40d198fa150c04150a6f219fa4ab7a8c054aa5538f23e63e95b2b4fd846
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/7.0.0 CPython/3.13.14

Security for EmptySpaceSearch 0.4.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page