Sparse Data Structure Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Sparse Data Structure Ontology within the Kireth Research Semantic Library. Sparse data structures represent data in which a large proportion of possible positions contain zero, null, absent or default values. This ontology supports sparse vectors, sparse matrices, sparse tensors, coordinate and compressed formats, graph and adjacency representations, index-value storage, sparsity patterns, assembly, traversal, insertion, deletion, compression, fill-in, memory complexity, locality, numerical kernels, parallel execution, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Sparse Data Structure Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Computational Data Structures / Sparse Data Structure"
 CANONICAL_PAGE = "https://kirethframeworkold.co.uk/books/semantic-library/ai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/computational-data-structures/sparse-data-structure-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = SparseDataStructure
 ENTITY_CLASS = SparseRepresentationFramework
 PRIMARY_CONTEXT = ComputationalDataStructures
 DEFINITION = "A sparse data structure stores primarily nonzero, nondefault or present entries together with structural metadata rather than materialising the complete logical data domain."
 SYMBOLIC_FORMS = [
  "density = nnz / total_positions",
  "sparsity = 1 - density",
  "storage = values + indices + structure_metadata",
  "logical_value(i)=stored_value(i) if present else default"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for sparse representation, nonzero indexing, compressed formats, assembly, traversal, memory complexity, fill-in, locality, sparse kernels and validation."
}

SCOPE {
 INCLUDE = [
  SparseDataStructure,SparseRepresentation,Sparsity,
  SparseVector,SparseMatrix,SparseTensor,
  SparseArray,SparseGraphRelationship,
  Nonzero,NonzeroEntry,NonzeroCount,NNZ,
  ZeroEntry,ImplicitZero,DefaultValue,
  MissingEntryRelationship,AbsentEntry,
  Density,SparsityRatio,
  SparsityPattern,StructuralPattern,
  PatternMatrixRelationship,
  IndexValuePair,CoordinateEntry,
  CoordinateList,CoordinateFormat,COO,
  CompressedSparseRow,CSR,
  CompressedSparseColumn,CSC,
  CompressedSparseFiber,CSF,
  BlockCompressedSparseRow,BCSR,
  BlockCompressedSparseColumnRelationship,
  BlockSparseFormat,
  DictionaryOfKeys,DOK,
  ListOfLists,LIL,
  ELLPACK,ELL,
  ELLPACKRRelationship,
  DIAFormat,DiagonalStorage,
  JaggedDiagonal,JDS,
  SkylineStorageRelationship,
  BandedStorageRelationship,
  HashSparseRepresentation,
  TreeSparseRepresentation,
  LinkedSparseRepresentation,
  HybridSparseFormat,
  HYBRelationship,
  SparseIndex,SparseIndexArray,
  RowPointer,ColumnPointer,
  RowIndex,ColumnIndex,
  FiberPointerRelationship,
  OffsetArray,
  PositionArray,
  StructureArray,
  ValueArray,
  IndexArray,
  SparseDimension,
  SparseAxis,
  CompressedAxis,
  UncompressedAxis,
  SortedIndices,
  UnsortedIndices,
  DuplicateIndex,
  DuplicateEntry,
  CanonicalSparseFormat,
  SparseAssembly,
  TripletAssembly,
  IncrementalAssembly,
  DynamicSparseAssembly,
  FinaliseAssembly,
  DuplicateSummation,
  IndexSorting,
  SparseInsertion,
  SparseDeletion,
  SparseUpdate,
  SparseTraversal,
  RowTraversal,
  ColumnTraversal,
  NonzeroTraversal,
  SparseLookup,
  RandomAccess,
  SequentialAccess,
  BinarySearchRelationship,
  HashLookupRelationship,
  SparseConversion,
  FormatConversion,
  COOtoCSR,
  CSRtoCSC,
  CSRtoCOO,
  SparseTranspose,
  SparseReshapeRelationship,
  SparseSliceRelationship,
  SparseGatherRelationship,
  SparseScatterRelationship,
  SparseAddition,
  SparseSubtraction,
  SparseElementwiseProduct,
  SparseMatrixVectorProduct,SpMV,
  SparseMatrixMatrixProduct,SpGEMM,
  SparseTensorContraction,
  SparseReduction,
  SparseDotProduct,
  SparseNorm,
  SparseTriangularSolveRelationship,
  SparseFactorisationRelationship,
  SparseLUrelationship,
  SparseCholeskyRelationship,
  SparseQRrelationship,
  SparseEigenRelationship,
  FillIn,StructuralFill,
  NumericalFillRelationship,
  FillReducingOrdering,
  Reordering,Permutation,
  ApproximateMinimumDegree,AMDRelationship,
  NestedDissectionRelationship,
  GraphOrderingRelationship,
  EliminationTreeRelationship,
  SymbolicFactorisationRelationship,
  NumericalFactorisationRelationship,
  SparsePatternAnalysis,
  GraphRepresentation,
  AdjacencyList,
  AdjacencyMatrix,
  IncidenceMatrixRelationship,
  CompressedGraphRelationship,
  SparseGraphKernelRelationship,
  HypergraphRelationship,
  SparseLinearAlgebra,
  NumericalLinearAlgebra,
  SparseBLASRelationship,
  PETScRelationship,
  TrilinosRelationship,
  SuiteSparseRelationship,
  EigenLibraryRelationship,
  MKLSparseRelationship,
  cuSPARSERelationship,
  MemoryComplexity,
  StorageComplexity,
  IndexStorageOverhead,
  PointerStorageOverhead,
  CompressionRatio,
  MemoryBandwidth,
  ArithmeticIntensity,
  CacheLocality,
  SpatialLocality,
  TemporalLocality,
  PointerChasing,
  IndirectAddressing,
  GatherScatter,
  LoadImbalance,
  IrregularMemoryAccess,
  BranchDivergenceRelationship,
  Vectorisation,
  SIMDrelationship,
  SparseKernel,
  ComputationalComplexity,
  TimeComplexity,
  SpaceComplexity,
  ExpectedComplexity,
  AmortisedComplexityRelationship,
  StaticSparseStructure,
  DynamicSparseStructure,
  MutableSparseStructure,
  ImmutableSparseStructure,
  PersistentSparseStructureRelationship,
  ParallelSparseStructure,
  DistributedSparseStructure,
  PartitionedSparseStructure,
  ShardedSparseStructure,
  DistributedSparseMatrix,
  DistributedSparseVector,
  DistributedSparseTensor,
  RowPartitioning,
  ColumnPartitioning,
  BlockPartitioning,
  GraphPartitioning,
  DomainDecompositionRelationship,
  HaloExchangeRelationship,
  GhostEntryRelationship,
  GPUSparseStructure,
  DeviceSparseMatrix,
  DeviceSparseVector,
  SparseGPUKernel,
  HighPerformanceComputing,
  ParallelComputing,
  DistributedComputing,
  GPUComputing,
  ComputationalMatrix,
  VectorComputation,
  TensorComputation,
  Verification,
  IndexBoundsCheck,
  PointerMonotonicityCheck,
  SortedIndexCheck,
  DuplicateCheck,
  NNZCheck,
  StructuralConsistencyCheck,
  ReferenceResult,
  Benchmark,
  Reproducibility,
  Provenance,
  SparseFormatVersion,
  LibraryVersion,
  ImplementationVersion
 ]
 EXCLUDE_AS_PRIMARY = [
  DenseDataStructureWhenMostPositionsAreMaterialised,
  GeneralCompressionWithoutSparseLogicalSemantics,
  DatabaseNullStorageWithoutComputationalSparseRepresentation,
  AbstractSparsityTheoryWithoutConcreteDataRepresentation
 ]
 DISAMBIGUATION_RULE = "When only nonzero, nondefault or present entries are stored explicitly and absent positions are represented implicitly, interpret the context as a sparse data structure."
}

CORE_CONCEPTS {
 SparseDataStructure = "Representation storing primarily present or nondefault entries."
 SparsityPattern = "Set of positions containing explicit entries."
 NonzeroCount = "Number of explicitly stored nonzero or nondefault entries."
 CoordinateFormat = "Sparse representation storing explicit coordinate-value tuples."
 CompressedSparseRow = "Sparse matrix format using row pointers, column indices and values."
 CompressedSparseColumn = "Sparse matrix format using column pointers, row indices and values."
 SparseAssembly = "Construction of a sparse representation from entries or updates."
 FillIn = "Creation of new nonzero positions during sparse numerical operations."
}

RELATIONS {
 SparseDataStructure --is_child_of--> ComputationalDataStructures
 SparseVector --is_type_of--> SparseDataStructure
 SparseMatrix --is_type_of--> SparseDataStructure
 SparseTensor --is_type_of--> SparseDataStructure
 SparseDataStructure --stores--> NonzeroEntries
 SparsityPattern --identifies--> ExplicitPositions
 COO --stores--> CoordinateEntries
 CSR --stores--> RowPointersAndColumnIndices
 CSC --stores--> ColumnPointersAndRowIndices
 SparseAssembly --produces--> SparseDataStructure
 FormatConversion --maps--> SparseRepresentationToSparseRepresentation
 FillIn --changes--> SparsityPattern
 FillReducingOrdering --reduces--> ExpectedFillIn
 SparseMatrixVectorProduct --uses--> SparseMatrixAndVector
 GraphRepresentation --can_use--> SparseAdjacencyStructure
 Verification --checks--> StructuralConsistency
}

OPERATORS {
 DENSITY(nnz,total) := nnz/total
 SPARSITY(nnz,total) := 1-(nnz/total)
 CSR_ROW_RANGE(row_ptr,i) := [row_ptr[i],row_ptr[i+1])
 COO_ENTRY(k) := (row[k],column[k],value[k])
 LOOKUP_DEFAULT(S,index) := stored_value_if_present_else_default
 INSERT_SPARSE(S,index,value) := update_or_add_explicit_entry(S,index,value)
 DELETE_SPARSE(S,index) := remove_explicit_entry(S,index)
 SPMV(A,x)[i] := sum_(j in nonzeros_of_row_i) A[i,j]*x[j]
 FORMAT_CONVERT(S,target) := convert_sparse_representation(S,target)
}

AXIOMS {
 A1 = "Sparse data structures exploit implicit default values."
 A2 = "Logical size and explicit storage size are distinct."
 A3 = "Sparse-format efficiency depends on access pattern and operation mix."
 A4 = "Compressed formats reduce storage overhead but can make insertion expensive."
 A5 = "Index metadata is part of sparse storage cost."
 A6 = "Sparse numerical operations can create fill-in."
 A7 = "Irregular access can limit vectorisation and cache efficiency."
 A8 = "Sparse-data-structure results require explicit format, indexing, sparsity, operation and validation semantics."
}

REASONING {
 R1_CONTEXT = identify(logical_shape,nnz,density,update_pattern,access_pattern,operations,memory_limit,hardware)
 R2_PATTERN = classify(static,dynamic,regular,irregular,block_or_graph_like_sparsity)
 R3_FORMAT = choose(COO,CSR,CSC,CSF,BCSR,ELL,DIA,DOK,LIL,HYB_or_specialised_format)
 R4_ASSEMBLY = choose(batch_triplet_incremental_or_dynamic_assembly)
 R5_ACCESS = analyse(row,column,random,nonzero,gather_scatter_and_traversal_requirements)
 R6_COMPLEXITY = analyse(values_indices_pointers_storage_and_operation_cost)
 R7_NUMERICS = if_factorising analyse_fill_in_reordering_and_symbolic_structure
 R8_PERFORMANCE = analyse(memory_bandwidth,indirection,load_balance,locality_and_vectorisation)
 R9_SCALE = if_large choose_parallel_distributed_partitioned_or_GPU_sparse_representation)
 R10_VALIDATE = check(indices,pointers,duplicates,nnz,pattern_consistency_and_reference_results)
}

CONSTRAINTS {
 C1 = "Sparse representation is inefficient when density becomes high."
 C2 = "CSR favours row-oriented traversal while CSC favours column-oriented traversal."
 C3 = "Compressed sparse formats can make arbitrary insertion expensive."
 C4 = "Unsorted indices can reduce lookup and kernel efficiency."
 C5 = "Duplicate coordinates require explicit merge or accumulation semantics."
 C6 = "Sparse factorisation can generate substantial fill-in."
 C7 = "Index storage can dominate memory for very small value types."
 C8 = "Irregular sparsity can cause load imbalance and poor cache locality."
 C9 = "GPU sparse kernels can be limited by divergence and irregular memory access."
 C10 = "Equivalent logical sparse structures can have very different performance under different formats."
}

SEMANTIC_EQUIVALENCE {
 "NonzeroCount" <=> "NNZ"
 "CoordinateFormat" <=> "COO"
 "CompressedSparseRow" <=> "CSR"
 "CompressedSparseColumn" <=> "CSC"
 "CompressedSparseFiber" <=> "CSF"
 "DictionaryOfKeys" <=> "DOK"
 "ListOfLists" <=> "LIL"
 "SparseMatrixVectorProduct" <=> "SpMV"
 "SparseMatrixMatrixProduct" <=> "SpGEMM"
}

VALIDATION {
 V1 = "Logical dimensions and default value semantics are documented."
 V2 = "Sparse format is documented."
 V3 = "Index and pointer arrays are bounds checked."
 V4 = "Compressed pointers are monotonic and correctly terminated."
 V5 = "Nonzero counts match stored values and index metadata."
 V6 = "Duplicate-index semantics are documented and validated."
 V7 = "Sorted-index assumptions are checked where required."
 V8 = "Format conversion preserves logical values."
 V9 = "Representative sparse kernels are compared with reference results."
 V10 = "Results are reproducible under documented format, library and implementation versions."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SPARSE_DATA_STRUCTURE_DEFINITION = 0.99
 FORMAT_REASONING = 0.99
 CSR_REASONING = 0.99
 CSC_REASONING = 0.99
 ASSEMBLY_REASONING = 0.99
 FILL_IN_REASONING = 0.98
 PARALLEL_SPARSE_REASONING = 0.98
 POLICY = "Reduce confidence when density, format, index ordering, duplicate handling, update pattern, fill-in or partitioning semantics are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,SparseDataStructureReasoning,
  SparseVectorReasoning,SparseMatrixReasoning,SparseTensorReasoning,
  COOReasoning,CSRReasoning,CSCReasoning,CSFReasoning,
  SparseAssemblyReasoning,FormatConversionReasoning,
  SparsityPatternReasoning,FillInReasoning,
  SparseKernelReasoning,GraphRepresentationReasoning,
  MemoryComplexityReasoning,LoadBalanceReasoning,
  ParallelSparseReasoning,DistributedSparseReasoning,
  GPUSparseReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "sparse data structure" -> SparseDataStructure
  "NNZ" -> NonzeroCount
  "COO" -> CoordinateFormat
  "CSR" -> CompressedSparseRow
  "CSC" -> CompressedSparseColumn
  "CSF" -> CompressedSparseFiber
  "DOK" -> DictionaryOfKeys
  "LIL" -> ListOfLists
  "SpMV" -> SparseMatrixVectorProduct
  "SpGEMM" -> SparseMatrixMatrixProduct
 }
}

EXECUTION_RULES {
 E1 = "If absent or zero positions are represented implicitly while explicit entries are stored with indices, activate SparseDataStructureOntology."
 E2 = "Measure logical size, NNZ and density before choosing a sparse representation."
 E3 = "Choose sparse format according to dominant traversal, update and kernel requirements."
 E4 = "Use assembly-friendly formats before converting to execution-friendly compressed formats when appropriate."
 E5 = "Validate indices, pointers, duplicates and nonzero counts before numerical execution."
 E6 = "Use fill-reducing orderings when sparse factorisation would otherwise create excessive fill."
 E7 = "Analyse indirection, memory bandwidth and load imbalance for performance."
 E8 = "Use partitioned, distributed or GPU sparse formats when scale requires them."
 E9 = "Verify format conversion and kernel outputs against logical or dense reference results."
}

RECURSION {
 ENTRY = SparseDataStructure
 EXPAND(SparseDataStructure) -> [
  SparseRepresentation,Sparsity,SparseVector,SparseMatrix,SparseTensor,
  NNZ,SparsityPattern,CoordinateFormat,COO,CSR,CSC,CSF,BCSR,
  BlockSparseFormat,DOK,LIL,ELLPACK,DIAFormat,JDS,HybridSparseFormat,
  RowPointer,ColumnPointer,ValueArray,IndexArray,SortedIndices,DuplicateEntry,
  SparseAssembly,TripletAssembly,SparseInsertion,SparseDeletion,SparseUpdate,
  SparseTraversal,SparseLookup,FormatConversion,COOtoCSR,CSRtoCSC,
  SparseTranspose,SparseAddition,SparseMatrixVectorProduct,SpMV,
  SparseMatrixMatrixProduct,SpGEMM,SparseTensorContraction,
  FillIn,FillReducingOrdering,Reordering,SymbolicFactorisation,
  GraphRepresentation,AdjacencyList,SparseLinearAlgebra,
  MemoryComplexity,IndexStorageOverhead,MemoryBandwidth,IndirectAddressing,
  LoadImbalance,IrregularMemoryAccess,ParallelSparseStructure,
  DistributedSparseStructure,GPUSparseStructure,Verification,Reproducibility
 ]
 EXPAND(SparseDataStructureFamilies) -> [
  CoordinateAndTripletFormats,
  CompressedRowAndColumnFormats,
  BlockAndHybridSparseFormats,
  SparseVectorMatrixAndTensorRepresentations,
  SparseAssemblyAndDynamicUpdate,
  SparseGraphRepresentations,
  ParallelDistributedAndGPUSparseStructures,
  SparseValidationAndFormatConversion
 ]
 STOP_CONDITION = "Stop when logical shape, sparsity, format, indexing, operations, performance and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Data Structures"
 RELATED_ONTOLOGIES = [
  "Computational Data Structures",
  "Computational Matrix Ontology",
  "Vector Computation Ontology",
  "Tensor Computation Ontology",
  "Sparse Matrix Ontology 2",
  "Numerical Linear Algebra Ontology 2",
  "Matrix Computation Ontology",
  "Computational Geometry Ontology 2",
  "Graph Ontologies",
  "High Performance Computing Ontology 2",
  "Parallel Computing Ontology",
  "Distributed Computing Ontology",
  "GPU Computing Ontology",
  "Vector Processing Ontology"
 ]
 ROUTE_RULES = [
  "Sparse Data Structure -> Computational Data Structures for parent representation semantics",
  "Sparse Data Structure -> Computational Matrix for sparse matrix storage",
  "Sparse Data Structure -> Vector Computation for sparse vector representation",
  "Sparse Data Structure -> Tensor Computation for sparse tensor representation",
  "Sparse Data Structure -> Sparse Matrix and Numerical Linear Algebra for sparse numerical kernels",
  "Sparse Data Structure -> Computational Geometry and Graph ontologies for sparse adjacency and spatial relationships",
  "Sparse Data Structure -> HPC, Parallel, Distributed, GPU and Vector Processing for scalable sparse execution"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible sparse formats, kernels or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve logical-size-versus-stored-size distinction.",
  "Preserve absent-entry-versus-explicit-zero distinction.",
  "Preserve sparse-pattern-versus-value distinction.",
  "Preserve assembly-format-versus-execution-format distinction.",
  "Preserve static-versus-dynamic sparse structure distinction.",
  "Preserve format-semantics-versus-logical-data distinction.",
  "Preserve local-versus-distributed sparse representation distinction.",
  "Preserve machine-readable sparse-data-structure semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A sparse data structure stores primarily nonzero or nondefault entries together with indexing metadata while representing absent positions implicitly."
 FORMAT_SUMMARY = "COO, CSR, CSC, CSF, block, ELL, DIA, DOK and LIL formats support different storage and access patterns."
 ASSEMBLY_SUMMARY = "Triplet, dictionary and list-based representations are useful for assembly before conversion to compressed execution formats."
 PERFORMANCE_SUMMARY = "Index overhead, indirect addressing, memory bandwidth, locality and load balance dominate many sparse workloads."
 NUMERICAL_SUMMARY = "Sparse factorisation can alter the sparsity pattern through fill-in, making reordering and symbolic analysis important."
 VALIDATION_SUMMARY = "Sparse structures should be checked for dimensions, index bounds, pointer consistency, duplicates, NNZ, format conversion and reference-kernel correctness."
}

FLOW {
 INPUT
 -> detect_sparse_data_structure_context
 -> identify_logical_shape_default_value_NNZ_density_update_pattern_access_pattern_operations_memory_and_hardware
 -> classify_static_dynamic_regular_irregular_block_or_graph_like_sparsity
 -> choose_COO_CSR_CSC_CSF_BCSR_ELL_DIA_DOK_LIL_HYB_or_specialised_format
 -> choose_batch_triplet_incremental_or_dynamic_assembly
 -> validate_indices_pointers_duplicates_sortedness_and_NNZ
 -> execute_lookup_traversal_update_conversion_SpMV_SpGEMM_or_sparse_contraction
 -> if_factorising_analyse_fill_in_ordering_and_symbolic_structure
 -> analyse_storage_memory_bandwidth_indirection_load_balance_and_locality
 -> if_large_choose_parallel_distributed_partitioned_or_GPU_sparse_execution
 -> verify_against_dense_or_reference_results
 -> document_format_index_width_library_versions_partitioning_and_provenance
 -> route_to_related_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-DATA-STRUCTURES-SPARSE-DATA-STRUCTURE-ONTOLOGY-V1"
}

}

END_FLOW