minMax99

MinMax99: A Novel Approach to Spatial Database Design for Djowda

Introduction

The MinMax99 spatial database system is an innovative solution developed for the Djowda platform. Its design addresses the critical challenges of managing large-scale, location-based data in a cost-effective and scalable manner. By dividing the Earth's surface into a precise grid and leveraging a unique hierarchical structure, MinMax99 enables efficient querying and data retrieval for millions of stores and stakeholders. The MinMax99 algorithm is used by the Djowda Intelligent Cell (DIC), which you can read more about here.

Key Design Goals

Efficiency:
- Minimize computational overhead for querying spatial data.
- Enable ultra-fast lookups for nearby locations.
Scalability:
- Handle billions of grid cells while maintaining lightweight data structures.
- Support future growth as the Djowda platform expands.
Cost-Effectiveness:
- Reduce reliance on costly centralized databases by using local computations and flat data storage.
- Optimize data storage and querying for Firebase or similar systems.
Innovative Integration:
- Seamlessly integrate with WebRTC for peer-to-peer communication.
- Ensure compatibility with real-time systems and offline-first applications.

This document provides an in-depth explanation of the MinMax99 system, covering its mathematical basis, data structures, and algorithms, and comparing its strengths and weaknesses to traditional spatial database systems.

Grid Table Design

The foundation of the MinMax99 system is a grid-based representation of the Earth's surface, enabling precise spatial indexing and efficient data retrieval. This section explains the grid's construction, its hierarchical structure, and the rationale behind its design.

2.1 Earth's Dimensions and Grid Resolution

Earth's Surface Dimensions:
- Approximate equatorial circumference: 40,075 km (40,075,000 m).
- Approximate pole-to-pole distance: 20,000 km (20,000,000 m).
Grid Cell Resolution:
- Each cell represents an area of 500 m x 500 m, chosen to balance precision with scalability.
- Total area per cell: 250,000 m².

2.2 Grid Structure

The MinMax99 grid divides the Earth's surface into a structured layout for efficient spatial indexing.

Rows and Columns

Columns:
(Earth's width / Cell size = 40,075,000 m / 500 m = 82,000)
Rows:
(Earth's height / Cell size = 20,000,000 m / 500 m = 42,000)

Note: The values 82,000 for columns and 42,000 for rows are specifically chosen to simplify and facilitate future calculations within the MinMax99 system.

Total Grid Cells

The total number of cells in the grid:
82,000 columns × 42,000 rows = 3,444,000,000 cells

Sequential Cell Numbering

Cells are assigned unique IDs, starting from top-left to bottom-right in a column-major order:
- Cell (0): Top-left corner ((x = 0, y = 0)).
- Cell (3,444,000,000): Bottom-right corner ((x = 81,999, y = 41,999)).

Example: Cell Numbering Table

Row/Column	0	1	2	...	81,999
0	Cell 0	Cell 42,000	Cell 84,000	...	Cell 3,441,999
1	Cell 1	Cell 42,001	Cell 84,001	...	Cell 3,442,000
2	Cell 2	Cell 42,002	Cell 84,002	...	Cell 3,442,001
...	...	...	...	...	...
41,999	Cell 41,999	Cell 83,999	Cell 125,999	...	Cell 3,444,000

2.3 Hierarchical Node Structure

To optimize scalability and querying, the grid is divided into hierarchical levels:

Level 1 (Top-Level Nodes):
- Represents groups of 1 million cells each.
- Number of nodes at this level: ⌈3,444,000,000 / 1,000,000⌉ = 3,444
Level 2 (Intermediate Nodes):
- Represents groups of 1,000 cells each within each Level 1 node.
- Number of nodes per Level 1 group: 1,000.
Level 3 (Leaf Nodes):
- Represents the individual cells at the finest granularity.

Advantages of the Grid Design

Scalability:
- Supports billions of cells with minimal computational overhead.
Efficient Querying:
- Hierarchical structure allows rapid narrowing of search space:
  - Top-Level Node → Intermediate Node → Individual Cell.
Logical Grouping:
- Provides logical separation for data organization and storage.
Compatibility with Firebase:
- Hierarchical paths align with Firebase’s real-time database structure, ensuring fast data access.

3. Mathematical Basis

The MinMax99 system relies on mathematical operations to map geo-coordinates to grid cells, assign unique identifiers, and determine spatial relationships efficiently.

3.1 Mapping Geo-Coordinates to Grid Cells

Geo-coordinates (latitude and longitude) are converted into grid cell coordinates using the Earth's dimensions and the defined cell resolution.

The key constants used in these calculations are:

EARTH_WIDTH_METERS: Approximate equatorial circumference (40,075,000 m).
EARTH_HEIGHT_METERS: Approximate pole-to-pole distance (20,000,000 m).
CELL_SIZE_METERS: Cell resolution (500 m).
NUM_COLUMNS: Calculated as EARTH_WIDTH_METERS / CELL_SIZE_METERS (82,000).
NUM_ROWS: Calculated as EARTH_HEIGHT_METERS / CELL_SIZE_METERS (42,000).

Latitude and Longitude to Meters

Convert longitude (`λ`) to the x-coordinate in meters:

x = (λ + 180) × (EARTH_WIDTH_METERS / 360)

Convert latitude (`φ`) to the y-coordinate in meters:

y = (EARTH_HEIGHT_METERS / 2) - ln(tan(π / 4 + φ × π / 360)) × (EARTH_HEIGHT_METERS / 2π)

Meters to Cell Coordinates

Determine the column (`x_cell`):

x_cell = floor(x / CELL_SIZE_METERS)

Determine the row (`y_cell`):

y_cell = floor(y / CELL_SIZE_METERS)

3.2 Cell Numbering

Each grid cell is assigned a unique numeric ID based on its column-major order:

Cell ID = x_cell × NUM_ROWS + y_cell

Example:

Latitude: 12.971598, Longitude: 77.594566 (approx. Bengaluru, India).
Step 1: Convert geo-coordinates to meters:

x = 26,689,774 m, y = 9,458,465 m

Step 2: Convert meters to cell coordinates:

x_cell = floor(26,689,774 / 500) = 53,379 y_cell = floor(9,458,465 / 500) = 18,916

Step 3: Calculate Cell ID:

Cell ID = (53,379 × 42,000) + 18,916 = 2,241,938,716

3.3 Neighbor Relationships

The MinMax99 system identifies neighboring cells by offsetting the row ((y_{\text{cell}})) and column ((x_{\text{cell}})) indices of the central cell.

Formulas for Neighboring Cells

Top Neighbor:

Cell ID_top = (x_cell × NUM_ROWS) + (y_cell - 1)

Bottom Neighbor:

Cell ID_bottom = (x_cell × NUM_ROWS) + (y_cell + 1)

Left Neighbor:

Cell ID_left = ((x_cell - 1) × NUM_ROWS) + y_cell

Right Neighbor:

Cell ID_right = ((x_cell + 1) × NUM_ROWS) + y_cell

Example:

Central Cell:
Cell ID = 2,241,938,716 (from previous calculation).

Coordinates:

x_cell = 53,379, y_cell = 18,916

Neighboring Cells:

Top Neighbor:

Cell ID_top = (53,379 × 42,000) + (18,916 - 1) = 2,241,938,715

Bottom Neighbor:

Cell ID_bottom = (53,379 × 42,000) + (18,916 + 1) = 2,241,938,717

Left Neighbor:

Cell ID_left = ((53,379 - 1) × 42,000) + 18,916 = 2,241,896,716

Right Neighbor:

Cell ID_right = ((53,379 + 1) × 42,000) + 18,916 = 2,241,980,716

3.4 Distance Calculations

The distance between two cells is approximated using the differences in their row and column indices:

Formula

Distance (in meters) = sqrt((Δx × CELL_SIZE_METERS)² + (Δy × CELL_SIZE_METERS)²)

Where:

( \Delta x = |x_{\text{cell1}} - x_{\text{cell2}}| )
( \Delta y = |y_{\text{cell1}} - y_{\text{cell2}}| )

Example

Cell 1: x_cell1 = 53,379, y_cell1 = 18,916
Cell 2: x_cell2 = 53,380, y_cell2 = 18,917

Step 1: Calculate differences in indices:

Δx = |53,379 - 53,380| = 1 Δy = |18,916 - 18,917| = 1

Step 2: Apply the formula:

Distance = sqrt((1 × 500)² + (1 × 500)²) = sqrt(250,000 + 250,000) = sqrt(500,000) ≈ 707.11 meters

4. Data Structures

The MinMax99 spatial database uses a combination of hierarchical and flat data structures to achieve efficient data storage and retrieval. This section explains the design and advantages of these structures.

4.1 Flat Data Structure

The flat structure organizes data directly by cell numbers, minimizing lookup complexity and ensuring fast access.

Structure Overview

Each cell number serves as a unique key, with associated data stored directly under it. For example:

store_stats/ <cell_number>/ <store_id>: { "isOpen": true, "updatedAt": "2024-10-26T14:00:00Z" } <store_id>: { "isOpen": false, "updatedAt": "2024-10-26T13:00:00Z" }

4. Data Structures

The MinMax99 spatial database combines hierarchical and flat data structures for efficient storage and retrieval. This section outlines the corrected structure based on the three-level hierarchy and flat storage strategy.

4.1 Flat Data Structure

The flat structure organizes data directly by cell numbers, enabling fast lookups for frequently accessed items.

Structure Overview

Each cell number serves as a unique key, with associated data stored directly under it. For example:

store_stats/ <cell_number>/ <store_id>: { "isOpen": true, "updatedAt": "2024-10-26T14:00:00Z" } <store_id>: { "isOpen": false, "updatedAt": "2024-10-26T13:00:00Z" }

Advantages

Fast Access:
- Direct lookup of data by cell number avoids multi-level traversal.
Scalability:
- Handles millions of store entries efficiently.
Lightweight:
- Optimized for operations requiring real-time responses.

4.2 Hierarchical Node Structure

The hierarchical structure logically partitions the dataset into progressively smaller groups, ensuring scalability.

Structure Overview

The hierarchy divides the grid as follows:

Level 1 (Top-Level Nodes):
- Represents groups of 1,000,000 cells, identified by ( \lfloor \text{cell_number} / 1,000,000 \rfloor ).
- Example: For cell_number = 2,241,938,716, Level 1 = 2241.
Level 2 (Intermediate Nodes):
- Represents groups of 1,000 cells within each top-level group, identified by ( \lfloor (\text{cell_number} / 1,000) \mod 1,000 \rfloor ).
- Example: For cell_number = 2,241,938,716, Level 2 = 938.
Level 3 (Leaf Nodes):
- Represents the individual cells, identified by ( \text{cell_number} \mod 1,000 ).
- Example: For cell_number = 2,241,938,716, Level 3 = 716.

Firebase Path Example

For cell_number = 2,241,938,716, the hierarchical path is:

Advantages

Fast Access:
- Direct lookup of data by cell number avoids multi-level traversal.
Scalability:
- Handles millions of store entries efficiently.
Lightweight:
- Optimized for operations requiring real-time responses.

store_data/ 2241/ 938/ 716/ <store_id>: { "name": "Store A", "inventory": { ... } }

Advantages

Efficient Querying:
- Reduces search space by narrowing down from Level 1 to Level 3.
Logical Partitioning:
- Simplifies data management and avoids overloading flat structures.
Firebase Compatibility:
- Well-suited for Firebase’s hierarchical design, enabling seamless data retrieval.

4.3 Choosing the Right Structure

MinMax99 strategically uses both structures:

Flat Data:
- Best for high-frequency operations like store availability checks.
Hierarchical Nodes:
- Ideal for scalable storage and operations involving multiple data points.

5. Algorithm Implementation

This section describes the core algorithms used in the MinMax99 system, including mapping geo-coordinates to cell numbers, constructing hierarchical database paths, and identifying neighboring cells.

5.1 Geo to Cell Number

This algorithm converts geo-coordinates (latitude and longitude) into a unique cell number based on the grid.

Pseudocode

function geoToCellNumber(latitude, longitude):
    EARTH_WIDTH_METERS = 40,075,000 // Earth's circumference in meters
    EARTH_HEIGHT_METERS = 20,000,000 // Earth's height in meters
    CELL_SIZE_METERS = 500 // Cell size in meters
    NUM_ROWS = 42000 // Number of rows in the grid

    // Convert longitude to x in meters
    xMeters = (longitude + 180) × (EARTH_WIDTH_METERS / 360)
    // Convert latitude to y in meters
    yMeters = (EARTH_HEIGHT_METERS / 2) - ln(tan(π / 4 + latitude × π / 360)) × (EARTH_HEIGHT_METERS / (2π))

    // Calculate cell coordinates
    xCell = floor(xMeters / CELL_SIZE_METERS)
    yCell = floor(yMeters / CELL_SIZE_METERS)

    // Compute cell number (column-major order)
    return (xCell × NUM_ROWS) + yCell

Example Latitude: 12.971598, Longitude: 77.594566 (Bengaluru, India). Step 1: Convert geo-coordinates to meters:

x = 26,689,774 m, y = 9,458,465 m

Step 2: Convert meters to cell coordinates:

xCell = floor(26,689,774 / CELL_SIZE_METERS) = 53,379

yCell = floor(9,458,465 / CELL_SIZE_METERS) = 18,916

Step 3: Calculate Cell ID:

Cell ID = (53,379 × NUM_ROWS) + 18,916 = 2,241,938,716

5.2 Constructing Firebase Paths This algorithm generates a hierarchical path for a given cell number.

Pseudocode

function constructDbPath(cellNumber, nodeName):
LEVEL1 = floor(cellNumber / 1,000,000) // Top-level node
LEVEL2 = floor((cellNumber / 1,000) % 1,000) // Intermediate node
LEVEL3 = cellNumber % 1,000 // Leaf node

    return LEVEL1 + "/" + LEVEL2 + "/" + LEVEL3 + "/" + nodeName

Example Cell Number: 2,241,938,716, Node Name: "store_data".

Firebase Path: 2241/938/716/store_data

5.3 Finding Neighboring Cells This algorithm identifies neighboring cells based on a given precision.

Pseudocode

function getNeighboringCells(cellNumber, precision):
CELL_SIZE_METERS = 500 // Grid cell size in meters
distance = floor(precision / CELL_SIZE_METERS) // Convert precision to cell units

    // Convert cell number to x, y coordinates
    xCell = floor(cellNumber / NUM_ROWS)
    yCell = cellNumber % NUM_ROWS

    neighbors = []

    // Iterate over neighboring cell range
    for dx in range(-distance, distance + 1):
        for dy in range(-distance, distance + 1):
            neighborX = xCell + dx
            neighborY = yCell + dy

            // Skip out-of-bounds neighbors
            if neighborX < 0 or neighborX >= NUM_COLUMNS or neighborY < 0 or neighborY >= NUM_ROWS:
                continue

            // Calculate neighbor cell number
            neighborCell = (neighborX × NUM_ROWS) + neighborY
            neighbors.append(neighborCell)

    return neighbors

Example Cell Number: 2,241,938,716 Precision (search extent): 1000m (results in a 5x5 cell area) Neighboring Cells:

[2,241,937,716, 2,241,939,716, 2,241,938,715, 2,241,938,717, ...]

5.4 Layer-Based Cell Retrieval

This section explains algorithms for retrieving cells based on "layers." In this context, a layer signifies a concentric square region around a central cell, with each layer stepping outwards at 5-kilometer intervals. This method is distinct from finding all cells within a precise radial distance (as in section 5.3) and is useful for queries where stepped, square-shaped regions are more appropriate.

Finding All Cells Within N Layers (`calculateCellsInLayers`)

This algorithm finds all cell IDs within a specified number of layers from an initial cell.

Pseudocode

function calculateCellsInLayers(initialCellID, layerNumber):
    // Assumes constants: NUM_ROWS, NUM_COLUMNS, CELL_SIZE_METERS
    // A "layer" here represents a 5000-meter step.

    x_cell = floor(initialCellID / NUM_ROWS)
    y_cell = initialCellID % NUM_ROWS

    // Convert layerNumber to a range in cell units
    // Each layer adds 5000m. Cell size is CELL_SIZE_METERS.
    // So, number of cell units for the step is 5000 / CELL_SIZE_METERS
    layer_step_in_cells = 5000 / CELL_SIZE_METERS
    max_offset_in_cells = layerNumber * layer_step_in_cells

    neighboringCellIDs = new List()

    for dx_step from -max_offset_in_cells to max_offset_in_cells step layer_step_in_cells:
        for dy_step from -max_offset_in_cells to max_offset_in_cells step layer_step_in_cells:
            // Optional: Skip the initial cell itself if dx_step and dy_step are both 0
            // if dx_step == 0 AND dy_step == 0:
            //     continue

            newX = x_cell + dx_step
            newY = y_cell + dy_step

            if newX >= 0 AND newX < NUM_COLUMNS AND newY >= 0 AND newY < NUM_ROWS:
                neighboringCellID = newX * NUM_ROWS + newY
                neighboringCellIDs.add(neighboringCellID)

    return neighboringCellIDs

Finding Cells on the Perimeter of a Specific Layer (`calculatePerimeterCellsOfLayer`)

This algorithm finds cell IDs that are specifically on the perimeter of a given layer number.

Pseudocode

function calculatePerimeterCellsOfLayer(initialCellID, layerNumber):
    // Assumes constants: NUM_ROWS, NUM_COLUMNS, CELL_SIZE_METERS
    // A "layer" here represents a 5000-meter step.

    x_cell = floor(initialCellID / NUM_ROWS)
    y_cell = initialCellID % NUM_ROWS

    layer_step_in_cells = 5000 / CELL_SIZE_METERS
    max_offset_in_cells = layerNumber * layer_step_in_cells

    layerCellIDs = new List()

    // Iterate to find cells at the perimeter of the square defined by max_offset_in_cells
    for dx_step from -max_offset_in_cells to max_offset_in_cells step layer_step_in_cells:
        for dy_step from -max_offset_in_cells to max_offset_in_cells step layer_step_in_cells:
            // Include only if it's on the border of the square layer
            if abs(dx_step) == max_offset_in_cells OR abs(dy_step) == max_offset_in_cells:
                newX = x_cell + dx_step
                newY = y_cell + dy_step

                if newX >= 0 AND newX < NUM_COLUMNS AND newY >= 0 AND newY < NUM_ROWS:
                    layerCellID = newX * NUM_ROWS + newY
                    layerCellIDs.add(layerCellID)

    return layerCellIDs

5.5 Determining Relative Cell Position

This algorithm determines the relative position of a target cell with respect to a reference cell (e.g., North, South-East, Same Cell). This is useful for understanding spatial relationships between two points on the grid.

Pseudocode

function determineRelativePosition(referenceCellID, targetCellID):
    // Assumes constants: NUM_ROWS

    // Convert referenceCellID to coordinates
    x_ref = floor(referenceCellID / NUM_ROWS)
    y_ref = referenceCellID % NUM_ROWS

    // Convert targetCellID to coordinates
    x_target = floor(targetCellID / NUM_ROWS)
    y_target = targetCellID % NUM_ROWS

    // Determine direction
    // Note: Assuming (0,0) is top-left.
    // Increasing y means moving South. Increasing x means moving East.

    if x_ref == x_target AND y_ref == y_target:
        return "Same Cell"
    else if x_ref == x_target:
        if y_target > y_ref:
            return "South" // Or "Bottom" if preferred for pure cardinal
        else:
            return "North" // Or "Top"
    else if y_ref == y_target:
        if x_target > x_ref:
            return "East" // Or "Right"
        else:
            return "West" // Or "Left"
    else:
        verticalDirection = ""
        if y_target > y_ref:
            verticalDirection = "South"
        else:
            verticalDirection = "North"

        horizontalDirection = ""
        if x_target > x_ref:
            horizontalDirection = "East"
        else:
            horizontalDirection = "West"

        return verticalDirection + "-" + horizontalDirection // e.g., "North-East"

Explanation of Output

The function returns a string indicating the relative position:

"Same Cell": If the reference and target cells are identical.
Cardinal Directions: "North", "South", "East", "West" if the target cell is directly along one of these axes relative to the reference cell.
Diagonal Directions: Combined strings like "North-East", "South-West", etc., for cells that are diagonally positioned.

Efficiency Direct Lookups: Single-cell queries are instantaneous due to numeric ID indexing. Regional Queries: Efficiently identify and query neighboring cells using the hierarchical structure. Scalability: Algorithms handle billions of cells with minimal computational overhead

6. Querying and Optimization

The MinMax99 system ensures efficient spatial data retrieval through well-structured queries and strategic optimizations. This section explains how queries are performed and optimized for scalability and performance.

6.1 Efficient Querying

Single-Cell Query

Directly retrieves data for a specific cell number.

Example:

Firebase Path:
```
store_stats/<cell_number>/<store_id>
```

Query retrieves:

{ "isOpen": true, "updatedAt": "2024-10-26T14:00:00Z" }

Regional Query

Retrieve data from multiple cells in a region:
1. Use geoToCellNumber to determine the central cell.
2. Use getNeighboringCells to calculate neighboring cells based on precision.
3. Perform parallel queries for all relevant cells.

6.2 Precision-Based Queries

Adjusting Query Precision

Precision determines the range of neighboring cells to include:
- 500m x 500m precision (single cell): Query only the center cell.
- 1.5km x 1.5km precision (3x3 cells): Include the center cell and its direct neighbors.
- Larger regions: Expand the range to include additional layers of neighbors.

Example: 1.5km x 1.5km Precision Query (3x3 cells)

Central Cell: 2,241,938,716
Neighbors:

[2,241,937,716, 2,241,939,716, 2,241,938,715, 2,241,938,717, ...]

Query all these cells to retrieve data for the region.

6.3 Optimizations

Hierarchical Querying

Use hierarchical paths to narrow the search space:
Level 1: Identify the relevant top-level node.
Level 2: Refine to the intermediate node.
Level 3: Access individual cell data.

Indexing

Leverage Firebase indexing for faster lookups:
Index paths by cell_number or updatedAt fields for real-time queries.

Caching

Cache frequently accessed data (e.g., store statuses) locally to reduce redundant queries.

Parallel Queries

Perform asynchronous queries for regional searches to improve response times:
Example: Query 10 neighboring cells simultaneously using multi-threading.

6.4 Scalability Strategies

Flat Structure for High-Frequency Queries

Use the flat structure for quick lookups like store availability checks.

Hierarchical Structure for Bulk Queries

Employ hierarchical nodes for larger operations, such as fetching data for multiple regions.

Optimized Data Updates

Update only relevant cells and users based on their spatial proximity to the change.

Performance Highlights

Single-Cell Query Time: Near-instantaneous due to direct lookup by cell number.
Regional Query Efficiency: Scales logarithmically with the size of the queried region.
Resource Efficiency: Combines WebRTC for real-time updates and Firebase for infrequent but necessary database interactions.

7. Practical Examples

This section provides step-by-step examples to demonstrate the functionality and efficiency of the MinMax99 system, from mapping geo-coordinates to querying data.

7.1 Mapping a User's Location to a Cell Number

Scenario

A user’s location: Latitude = 12.971598, Longitude = 77.594566.

Steps

Convert Geo-Coordinates to Meters:

x = (77.594566 + 180) × (40,075,000 / 360) = 26,689,774 m y = (20,000,000 / 2) - ln(tan(π / 4 + (12.971598 × π / 360))) × (20,000,000 / (2π)) = 9,458,465 m

Convert Meters to Cell Coordinates:

x_cell = floor(26,689,774 / 500) = 53,379 y_cell = floor(9,458,465 / 500) = 18,916

Calculate the Cell Number:

Cell ID = (53,379 × 42,000) + 18,916 = 2,241,938,716

7.2 Querying Store Availability

Scenario

Querying for the store status in cell 2,241,938,716.

Steps

Firebase Path:
store_stats/2,241,938,716/<store_id>
Retrieved Data:
{ "isOpen": true, "updatedAt": "2024-10-26T14:00:00Z" }

7.3 Regional Query for Nearby Stores

Scenario

The user wants to find all nearby stores within a 1.5km x 1.5km precision (3x3 cells) region.

Steps

Identify Neighboring Cells:

Center Cell ID = 2,241,938,716 Precision = 1.5km x 1.5km (3x3 cells) Neighbors = [2,241,937,715, 2,241,937,716, 2,241,937,717, 2,241,938,715, ...]

Query Firebase:
Perform parallel queries for each cell in the list:

store_stats/<cell_number>/<store_id>

Consolidate Results:
Combine responses into a unified list of stores, filtering based on criteria (e.g., isOpen = true).

7.4 Constructing a Firebase Path

Scenario

Storing inventory data for a store in cell 2,241,938,716.

Steps

Cell Number Hierarchy:

Level 1 = floor(2,241,938,716 / 1,000,000) = 2241 Level 2 = floor((2,241,938,716 / 1,000) % 1,000) = 938 Level 3 = 2,241,938,716 % 1,000 = 716

Firebase Path:

store_data/2241/938/716/<store_id>

Store Inventory:

{ "name": "Store A", "inventory": { "apples": { "price": 2.5, "quantity": 50 }, "bananas": { "price": 1.2, "quantity": 100 } }, "isOpen": true }

7.5 Distance Calculation Between Two Stores

Scenario

Store 1 in 2,241,938,716.
Store 2 in 2,241,939,717.

Steps

Extract Coordinates:

x1 = floor(2,241,938,716 / 42,000) = 53,379 y1 = 2,241,938,716 % 42,000 = 18,916

x2 = floor(2,241,939,717 / 42,000) = 53,379 y2 = 2,241,939,717 % 42,000 = 18,917

Calculate Differences:

Δx = |53,379 - 53,379| = 0 Δy = |18,916 - 18,917| = 1

Compute Distance:

Distance = sqrt((Δx × 500)² + (Δy × 500)²) = sqrt(0² + 500²) = 500 meters

🌐 Lobby System (Spatial Communication Layer)

The Lobby System is a key architectural feature of MinMax99 that enables efficient, scalable, and localized communication across the map grid.

🔷 Structure

Each MinMax99 Cell: Represents a 500m × 500m square (250,000 m²).
Lobby Block: A logical group of 20 × 20 cells, covering a 10km × 10km area.
Client View: Each client (e.g., user or store app) subscribes to a 3 × 3 grid of lobbies (30km × 30km) centered on its current position.
Note: The Lobby Grid uses Column-Major Order, aligned with the MinMax99 cell grid structure, to ensure consistent spatial indexing and traversal.

📡 Purpose

Scopes MQTT communication by limiting message flow to local zones.
Reduces network noise and improves real-time responsiveness.
Facilitates discovery of nearby entities (stores, users, deliveries, etc.) within relevant proximity.
Each lobby acts as a communication topic, e.g., lobby/123_456.

🧭 Lobby ID Calculation

int lobbyX = cellX / 20;
int lobbyY = cellY / 20;
String topic = "lobby/" + lobbyX + "_" + lobbyY;

📍 Subscription Strategy

Clients automatically subscribe to their current lobby and its 8 neighbors:

for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
        int lx = lobbyX + dx;
        int ly = lobbyY + dy;
        subscribe("lobby/" + lx + "_" + ly);
    }
}

This setup keeps each client aware of activity in its local zone while maintaining scalability across a global grid.

8. Comparison with Existing Spatial Databases

The MinMax99 spatial database design offers a unique approach to managing large-scale location-based data. This section compares MinMax99 to traditional spatial databases, highlighting its strengths and weaknesses.

8.1 Overview of Existing Systems

Common spatial database approaches include:

Quadtrees:
- A tree structure that recursively subdivides space into quadrants.
- Ideal for managing sparse data but can be inefficient for uniform datasets.
R-Trees:
- Organizes data into rectangles for efficient range queries.
- Commonly used in GIS systems for spatial indexing.
Geohashing:
- Encodes geo-coordinates into hash strings at varying precision levels.
- Efficient for proximity queries but less intuitive for hierarchical navigation.
Z-Order Curves:
- Maps multi-dimensional data into a one-dimensional space.
- Useful for range queries but computationally intensive.

8.2 Strengths of MinMax99

Efficient Grid-Based Design:
- Simplifies spatial indexing by dividing the Earth's surface into uniform cells.
- Fixed resolution (500m x 500m) eliminates the complexity of dynamic subdivisions.
Hierarchical Structure:
- Combines flat data storage with logical groupings for scalability.
- Allows rapid narrowing of search space in large datasets.
Lightweight and Cost-Effective:
- Designed for platforms like Firebase, minimizing server costs.
- No need for specialized spatial indexing libraries or extensions.
Real-Time Integration:
- Built for seamless use with WebRTC for direct app-to-app communication.

8.3 Weaknesses of MinMax99

Fixed Resolution:
- Lacks dynamic zoom-level adjustments for fine-grained precision.
Limited Geometric Queries:
- Not optimized for complex spatial operations like polygon intersections or nearest-neighbor in irregular shapes.
Dependence on Predefined Structures:
- Relies on column-major ordering, which may not align with all database use cases.

8.4 Use Cases Comparison

Feature	MinMax99	Quadtrees	R-Trees	Geohashing	Z-Order Curves
Precision	Fixed (500m x 500m)	Adjustable	Adjustable	Adjustable	Adjustable
Scalability	High, hierarchical grouping	Medium	High	High	High
Efficiency for Lookups	Very high (direct cell lookups)	Medium	High	High	Medium
Geometric Queries	Limited	High	Very High	Medium	Medium
Integration Cost	Low (Firebase/WebRTC-ready)	Medium	High	Low	Medium

Conclusion

MinMax99 excels in scenarios requiring cost-effective, scalable, and lightweight spatial indexing. While it may lack advanced geometric operations, its efficiency for real-time querying and compatibility with modern app frameworks make it a powerful choice for location-based services.

9. Conclusion and Future Enhancements

The MinMax99 spatial database system offers an innovative and efficient solution for managing large-scale, location-based data. By combining a fixed-resolution grid with a hierarchical data structure, it achieves the following key goals:

Scalability: Handles billions of entries with logical data partitioning.
Efficiency: Provides rapid lookups and optimized queries using column-major ordering.
Cost-Effectiveness: Reduces reliance on costly spatial database extensions while maintaining compatibility with Firebase and WebRTC.

While MinMax99 is well-suited for the current needs of the Djowda platform, its flexibility ensures that it can evolve to address future challenges.

Future Enhancements

To further optimize and enhance the MinMax99 system, the following advancements are planned:

1. Higher Precision Grids

Introduce a finer-resolution grid for each 500m x 500m cell by dividing it into smaller squares (e.g., (500 \times 500) grid with 1m² precision).
Each sub-cell will have its unique ID relative to the parent 500m x 500m cell.

Proposed Structure for 1m² Precision:

Within a 500m x 500m cell, create a (500 \times 500) table:
- Sub-cell IDs range from 0,0 to 499,499.
Use a hierarchical path to reference both the parent cell and the sub-cell: store_data/<parent_cell>/<sub_cell_x>/<sub_cell_y>/<store_id>

2. Enhanced Query Precision

Allow dynamic zoom levels to switch between the 500m² grid and the finer 1m² sub-grid.
Implement queries that adapt precision based on application requirements (e.g., zooming in for detailed mapping or proximity detection).

3. AI-Powered Spatial Analytics

Integrate AI models to predict high-traffic areas and cache frequently accessed cells.
Enable real-time optimization of regional queries based on usage patterns.

4. Geometric Query Support

Extend the system to support advanced geometric operations, such as polygon-based searches or pathfinding within a grid.

5. Distributed Data Handling

Implement mechanisms to distribute grid data across multiple nodes or regions for enhanced scalability and reliability.

Version History

Version	Date	Description
v1.0	2024-11-19	Initial version with 500m² precision and hierarchical structure.
v1.1	Planned	Finer-resolution grid at 1m² precision with sub-cell ID system.
v2.0	Planned	Support for AI-driven optimizations and advanced geometric queries.

Closing Remarks

MinMax99 represents a significant step toward achieving scalable and efficient spatial data management for the Djowda platform. Its current implementation addresses key challenges in location-based systems, while future enhancements promise to extend its capabilities, ensuring it remains adaptable to emerging needs.

Name		Name	Last commit message	Last commit date
Latest commit History 33 Commits
docs		docs
LICENSE		LICENSE
README.md		README.md

License

Moses-Code-Dev/minMax99

Folders and files

Latest commit

History

Repository files navigation

minMax99

Table of Contents

MinMax99: A Novel Approach to Spatial Database Design for Djowda

Introduction

Key Design Goals

Grid Table Design

2.1 Earth's Dimensions and Grid Resolution

2.2 Grid Structure

Rows and Columns

Total Grid Cells

Sequential Cell Numbering

Example: Cell Numbering Table

2.3 Hierarchical Node Structure

Advantages of the Grid Design

3. Mathematical Basis

3.1 Mapping Geo-Coordinates to Grid Cells

Latitude and Longitude to Meters

Meters to Cell Coordinates

3.2 Cell Numbering

Example:

3.3 Neighbor Relationships

Formulas for Neighboring Cells

Example:

3.4 Distance Calculations

Formula

Example

4. Data Structures

4.1 Flat Data Structure

Structure Overview

4. Data Structures

4.1 Flat Data Structure

Structure Overview

Advantages

4.2 Hierarchical Node Structure

Structure Overview

Firebase Path Example

Advantages

Advantages

4.3 Choosing the Right Structure

5. Algorithm Implementation

5.1 Geo to Cell Number

Pseudocode

5.4 Layer-Based Cell Retrieval

Finding All Cells Within N Layers (calculateCellsInLayers)

Pseudocode

Finding Cells on the Perimeter of a Specific Layer (calculatePerimeterCellsOfLayer)

Pseudocode

5.5 Determining Relative Cell Position

Pseudocode

Explanation of Output

6. Querying and Optimization

6.1 Efficient Querying

Single-Cell Query

Regional Query

6.2 Precision-Based Queries

Adjusting Query Precision

Example: 1.5km x 1.5km Precision Query (3x3 cells)

6.3 Optimizations

Hierarchical Querying

Indexing

Caching

Parallel Queries

6.4 Scalability Strategies

Flat Structure for High-Frequency Queries

Hierarchical Structure for Bulk Queries

Optimized Data Updates

Performance Highlights

7. Practical Examples

7.1 Mapping a User's Location to a Cell Number

Scenario

Steps

7.2 Querying Store Availability

Scenario

Steps

Finding All Cells Within N Layers (`calculateCellsInLayers`)

Finding Cells on the Perimeter of a Specific Layer (`calculatePerimeterCellsOfLayer`)

Packages