Struct LinearDetector 

pub struct LinearDetector { /* private fields */ }

Linear pattern detection state machine.

Tracks consecutive degree-1 steps during graph traversal to detect linear access patterns. Once linear pattern is confirmed (3+ consecutive steps), the detector can trigger sequential I/O optimization.

Fields

• state: Current detector state (Unknown, Accumulating, Linear, Branching)
• consecutive_linear: Count of consecutive degree-1 steps observed
• threshold: Number of consecutive degree-1 steps required to confirm Linear (default: 3)
• cluster_offsets: History of (cluster_offset, cluster_size) tuples observed during traversal
• chains_detected: Number of chains detected during traversal (Phase 33)
• total_chain_length: Cumulative length of all detected chains (Phase 33)
• time_linear_detection_ns: Total time spent in pattern detection (nanoseconds)
• time_contiguity_validation_ns: Total time spent in contiguity validation (nanoseconds)

Cluster Offset Tracking (Phase 33)

The cluster_offsets field stores the offset and size of each edge cluster visited during traversal. This enables contiguity validation in Phase 34-35:

• Sequential cluster reads require clusters to be contiguous on disk
• Tracking offsets during traversal avoids additional I/O for validation
• Offsets are cleared on reset() to maintain per-traversal isolation

Timing Instrumentation (Phase 37)

The time_linear_detection_ns and time_contiguity_validation_ns fields accumulate timing information for diagnostic telemetry. These help identify performance bottlenecks during Chain(500) traversal analysis.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Observe nodes during traversal
detector.observe(1, 1); // degree 1
detector.observe(2, 1); // degree 1
detector.observe(3, 1); // degree 1 -> Linear confirmed!

assert!(detector.is_linear_confirmed());
assert_eq!(detector.confidence(), 1.0);

// Reset for new traversal
detector.reset();
assert!(!detector.is_linear_confirmed());
assert_eq!(detector.confidence(), 0.0);

Implementations

impl LinearDetector

pub fn new() -> Self

Create new detector with default threshold (3 steps).

The threshold of 3 consecutive degree-1 steps prevents false positives on tree graphs which often have 1-2 linear segments before branching.

Example

use crate::backend::native::adjacency::LinearDetector;

let detector = LinearDetector::new();
assert_eq!(detector.confidence(), 0.0);
assert!(!detector.is_linear_confirmed());

pub fn with_threshold(threshold: u32) -> Self

Create new detector with custom threshold.

Useful for testing with different threshold values. Lower thresholds increase false positive rate on trees; higher thresholds may miss legitimate linear patterns.

Parameters

• threshold: Minimum consecutive degree-1 steps to confirm Linear pattern

Example

use crate::backend::native::adjacency::LinearDetector;

// Detector with threshold of 5 (more conservative)
let detector = LinearDetector::with_threshold(5);

pub fn observe( &mut self, _node_id: NativeNodeId, degree: u32, ) -> TraversalPattern

Observe a node during traversal.

This is the core state machine method. It takes a node ID and its degree, updates internal state, and returns the current pattern classification.

State Machine Logic

• Branching state: Immediately return Branching (terminal state)
• Linear state with degree > 1: Transition to Branching, return Branching
• Linear state with degree <= 1: Stay in Linear, return Linear
• Unknown/Accumulating with degree > 1: Transition to Branching, return Branching
• Unknown/Accumulating with degree == 1: Increment counter, check threshold
• Unknown/Accumulating with degree == 0: Stay in Unknown, return Unknown

Parameters

• node_id: The node being observed (for debugging/logging, not used in state logic)
• degree: The node’s degree (typically from AdjacencyHelpers::outgoing_degree())

Returns

The current TraversalPattern classification after this observation.

Example

use crate::backend::native::adjacency::{LinearDetector, TraversalPattern};

let mut detector = LinearDetector::new();

// Chain graph: 1 -> 2 -> 3 -> 4
assert_eq!(detector.observe(1, 1), TraversalPattern::Unknown);
assert_eq!(detector.observe(2, 1), TraversalPattern::Unknown);
assert_eq!(detector.observe(3, 1), TraversalPattern::Linear); // threshold reached
assert_eq!(detector.observe(4, 1), TraversalPattern::Linear);  // stays Linear

pub fn observe_with_cluster( &mut self, node_id: NativeNodeId, degree: u32, cluster_offset: u64, cluster_size: u32, ) -> TraversalPattern

Observe a node with its cluster information.

This method extends observe() by also recording cluster offset and size for contiguity validation in Phase 34. It performs the same degree-based pattern detection as observe() while building a history of cluster locations.

Parameters

• node_id: The node being observed
• degree: The node’s degree (typically from AdjacencyHelpers::outgoing_degree())
• cluster_offset: Byte offset of the node’s edge cluster in the graph file
• cluster_size: Size of the edge cluster in bytes

Returns

The current TraversalPattern classification after this observation.

Example

use crate::backend::native::adjacency::{LinearDetector, TraversalPattern};

let mut detector = LinearDetector::new();

// Observe nodes with cluster information
assert_eq!(
    detector.observe_with_cluster(1, 1, 1024, 4096),
    TraversalPattern::Unknown
);
assert_eq!(
    detector.observe_with_cluster(2, 1, 5120, 4096),
    TraversalPattern::Unknown
);
assert_eq!(
    detector.observe_with_cluster(3, 1, 9216, 4096),
    TraversalPattern::Linear
);

// Cluster offsets are recorded for contiguity validation
let offsets = detector.cluster_offsets();
assert_eq!(offsets.len(), 3);
assert_eq!(offsets[0], (1024, 4096));
assert_eq!(offsets[1], (5120, 4096));
assert_eq!(offsets[2], (9216, 4096));

pub fn cluster_offsets(&self) -> &[(u64, u32)]

Get the recorded cluster offsets.

Returns a slice of (offset, size) tuples representing the clusters observed during traversal. This enables contiguity validation in Phase 34.

Returns

Slice of (cluster_offset, cluster_size) tuples.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

detector.observe_with_cluster(1, 1, 1024, 4096);
detector.observe_with_cluster(2, 1, 5120, 4096);

let offsets = detector.cluster_offsets();
assert_eq!(offsets.len(), 2);
assert_eq!(offsets[0], (1024, 4096));
assert_eq!(offsets[1], (5120, 4096));

pub fn record_chain(&mut self, length: u32)

Record a detected chain for instrumentation.

This method is called when a linear chain is detected during traversal. It increments the chain counter and accumulates the chain length for average chain length calculation.

Parameters

• length: The length of the detected chain (number of nodes/edges)

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Record a chain of length 10
detector.record_chain(10);
assert_eq!(detector.chain_count(), 1);
assert_eq!(detector.total_chain_length(), 10);

// Record another chain of length 5
detector.record_chain(5);
assert_eq!(detector.chain_count(), 2);
assert_eq!(detector.total_chain_length(), 15);

pub fn confidence(&self) -> f64

Get confidence score (0.0 to 1.0).

Confidence indicates how certain the detector is that the current traversal is linear:

• 1.0: Confirmed Linear (threshold+ consecutive degree-1 steps)
• 0.0 < x < 1.0: Accumulating (progress toward threshold, e.g., 2/3 = 0.67)
• 0.0: Unknown or Branching

Returns

Confidence score in range [0.0, 1.0].

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

assert_eq!(detector.confidence(), 0.0); // Initial state

detector.observe(1, 1);
assert_eq!(detector.confidence(), 1.0 / 3.0); // 1/3 ≈ 0.33

detector.observe(2, 1);
assert_eq!(detector.confidence(), 2.0 / 3.0); // 2/3 ≈ 0.67

detector.observe(3, 1);
assert_eq!(detector.confidence(), 1.0); // Confirmed Linear

pub fn reset(&mut self)

Reset detector state (for new traversal).

Clears all state and returns the detector to initial Unknown condition. Call this when starting a new traversal or reusing a detector instance.

This also clears the cluster offset history and chain instrumentation, ensuring per-traversal isolation.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// First traversal
detector.observe(1, 1);
detector.observe(2, 1);
detector.observe(3, 1);
assert!(detector.is_linear_confirmed());

detector.record_chain(10);
assert_eq!(detector.chain_count(), 1);

// Reset for second traversal
detector.reset();
assert!(!detector.is_linear_confirmed());
assert_eq!(detector.confidence(), 0.0);
assert_eq!(detector.cluster_offsets().len(), 0);
assert_eq!(detector.chain_count(), 0);

pub fn current_pattern(&self) -> TraversalPattern

Get current pattern without observation.

Returns the current pattern classification without modifying state. Useful for checking detector state between observations.

Returns

The current TraversalPattern classification.

Example

use crate::backend::native::adjacency::{LinearDetector, TraversalPattern};

let mut detector = LinearDetector::new();

assert_eq!(detector.current_pattern(), TraversalPattern::Unknown);

detector.observe(1, 1);
assert_eq!(detector.current_pattern(), TraversalPattern::Unknown);

detector.observe(2, 1);
detector.observe(3, 1);
assert_eq!(detector.current_pattern(), TraversalPattern::Linear);

pub fn is_linear_confirmed(&self) -> bool

Check if linear pattern is confirmed.

Returns true if the detector has observed threshold+ consecutive degree-1 steps and is in Linear state. This is the primary method to check whether sequential I/O optimization should be enabled.

Returns

true if linear pattern is confirmed (confidence >= 1.0), false otherwise.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

assert!(!detector.is_linear_confirmed());

detector.observe(1, 1);
assert!(!detector.is_linear_confirmed());

detector.observe(2, 1);
assert!(!detector.is_linear_confirmed());

detector.observe(3, 1);
assert!(detector.is_linear_confirmed()); // threshold reached!

pub fn chain_count(&self) -> u64

Get the number of chains detected during traversal.

Returns the count of chains that have been recorded via record_chain(). This metric helps validate the effectiveness of chain detection for IO-12.

Returns

Number of chains detected (0 if none).

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

assert_eq!(detector.chain_count(), 0);

detector.record_chain(10);
assert_eq!(detector.chain_count(), 1);

detector.record_chain(5);
assert_eq!(detector.chain_count(), 2);

pub fn total_chain_length(&self) -> u64

Get the total accumulated length of all detected chains.

Returns the sum of lengths of all chains recorded via record_chain(). Combined with chain_count(), this enables calculating average chain length.

Returns

Total chain length across all detected chains (0 if none).

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

assert_eq!(detector.total_chain_length(), 0);

detector.record_chain(10);
assert_eq!(detector.total_chain_length(), 10);

detector.record_chain(5);
assert_eq!(detector.total_chain_length(), 15);

pub fn average_chain_length(&self) -> f64

Get the average length of detected chains.

Returns the mean chain length across all chains recorded via record_chain(). Returns 0.0 if no chains have been detected.

Returns

Average chain length as f64, or 0.0 if no chains detected.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// No chains: average is 0.0
assert_eq!(detector.average_chain_length(), 0.0);

detector.record_chain(10);
assert_eq!(detector.average_chain_length(), 10.0);

detector.record_chain(20);
// Average: (10 + 20) / 2 = 15.0
assert_eq!(detector.average_chain_length(), 15.0);

pub fn validate_contiguity(&mut self) -> bool

Validate that recorded cluster offsets form a contiguous sequence on disk.

Contiguity is required for sequential I/O optimization to provide benefit. Non-contiguous clusters read sequentially are still random I/O from the disk’s perspective.

Returns

true if clusters are contiguous, false otherwise. Returns false if fewer than 2 clusters have been recorded (contiguity is meaningless for a single cluster).

Contiguity Definition

Clusters are contiguous if each cluster starts immediately after the previous one ends: offsets[i+1] == offsets[i] + sizes[i]

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Empty history: not contiguous
assert!(!detector.validate_contiguity());

// Single cluster: not contiguous (need >=2)
detector.observe_with_cluster(1, 1, 1024, 4096);
assert!(!detector.validate_contiguity());

// Two contiguous clusters: 1024 + 4096 = 5120
detector.observe_with_cluster(2, 1, 5120, 4096);
assert!(detector.validate_contiguity());

// Third cluster creates a gap
detector.observe_with_cluster(3, 1, 10000, 4096); // should be 9216
assert!(!detector.validate_contiguity());

pub fn time_linear_detection_ms(&self) -> f64

Get total time spent in linear pattern detection (milliseconds).

Returns the accumulated time for all calls to observe() and observe_with_cluster(). This is diagnostic instrumentation for Phase 37 gap analysis.

Returns

Total detection time in milliseconds (converted from nanoseconds).

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Perform observations
for i in 1..=100 {
    detector.observe(i, 1);
}

// Get accumulated timing
let detection_ms = detector.time_linear_detection_ms();

pub fn time_contiguity_validation_ms(&self) -> f64

Get total time spent in contiguity validation (milliseconds).

Returns the accumulated time for all calls to validate_contiguity(). This is diagnostic instrumentation for Phase 37 gap analysis.

Returns

Total validation time in milliseconds (converted from nanoseconds).

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Perform observations with cluster info
detector.observe_with_cluster(1, 1, 1024, 4096);
detector.observe_with_cluster(2, 1, 5120, 4096);

// Validate contiguity multiple times
let _ = detector.validate_contiguity();
let _ = detector.validate_contiguity();

// Get accumulated timing
let validation_ms = detector.time_contiguity_validation_ms();

pub fn should_use_sequential_read(&mut self) -> bool

Check if sequential read path should be used.

This is the single boolean check that traversal code uses to decide whether to use sequential cluster reads (Phase 34) or the standard path.

When to Call

Call this method after observe_with_cluster() once the traversal has accumulated enough observations. The method returns true only when:

1. The pattern is confirmed linear (is_linear_confirmed())
2. The clusters are contiguous on disk (validate_contiguity())

Both conditions are required for sequential I/O to provide benefit.

Integration with Phase 34

When this returns true, the traversal can use SequentialClusterReader to read all clusters for a chain in a single I/O operation. This provides the performance optimization target for IO-12 (Chain(500) <= 75ms).

Relationship with TraversalContext

The detector is per-traversal (stored in TraversalContext or local to the traversal function). This preserves MVCC isolation and prevents cross-traversal state leakage.

Returns

true if both linear pattern is confirmed AND clusters are contiguous, false otherwise.

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Before threshold: false
detector.observe_with_cluster(1, 1, 1024, 4096);
assert!(!detector.should_use_sequential_read());

// Still before threshold: false
detector.observe_with_cluster(2, 1, 5120, 4096);
assert!(!detector.should_use_sequential_read());

// Linear confirmed + contiguous: true
detector.observe_with_cluster(3, 1, 9216, 4096);
assert!(detector.should_use_sequential_read());

// Non-contiguous clusters: false
detector.reset();
detector.observe_with_cluster(1, 1, 1024, 4096);
detector.observe_with_cluster(2, 1, 5120, 4096);
detector.observe_with_cluster(3, 1, 10000, 4096); // Gap: should be 9216
assert!(!detector.should_use_sequential_read());

pub fn predicted_chain_length(&self) -> usize

Predict the total chain length based on current observations.

This method provides an estimate of the final chain length for allocation-aware optimization (Phase 40). The prediction is used to determine whether to trigger contiguous allocation during writes.

Prediction Strategy

• Linear confirmed: Returns the max of cluster_offsets.len() and consecutive_linear (handles both observe() and observe_with_cluster() usage)
• Accumulating: Returns the current consecutive linear count
• Unknown/Branching: Returns 0 (no chain detected)

Integration with Write-Path Optimization

When writing clusters, this method can be called to predict the chain length:

• If predicted >= CHAIN_THRESHOLD, trigger contiguous allocation
• Otherwise, use normal fragmented allocation

Returns

Predicted chain length as usize (number of clusters/nodes in the chain).

Example

use crate::backend::native::adjacency::LinearDetector;

let mut detector = LinearDetector::new();

// Initial state: no prediction
assert_eq!(detector.predicted_chain_length(), 0);

// Observing linear pattern
detector.observe(1, 1);
assert_eq!(detector.predicted_chain_length(), 1);

detector.observe(2, 1);
assert_eq!(detector.predicted_chain_length(), 2);

// After threshold: prediction uses cluster_offsets
detector.observe_with_cluster(3, 1, 9216, 4096);
assert_eq!(detector.predicted_chain_length(), 3);

pub fn observed_length(&self) -> usize

Get the current observed chain length (number of linear steps observed).

This is a helper for accessing the raw consecutive linear count. For most use cases, predicted_chain_length() is preferred.

Returns

Number of consecutive linear steps observed so far.

Trait Implementations

impl Default for LinearDetector

fn default() -> Self

Returns the “default value” for a type.