Benchmark Dataset for Large-Scale Streaming Validation with Hedge Automata

Synthetic JSON Dataset Generator. To evaluate the scalability of hedge automata algorithms, we developed a recursive JSON dataset generator. The generator produces synthetic JSON documents with controllable structural parameters, allowing the independent evaluation of vertical and horizontal scalability. A generated document follows a recursive grammar where a document contains an object, an object consists of a configurable number of members, and arrays contain a configurable number of nested objects. The generation process is controlled by three main parameters: the maximum nesting depth, the number of members per object, and the array size. The depth parameter controls the vertical dimension of the generated trees, while the number of members and array size control the horizontal dimension represented by hedge sequences. The generator recursively expands objects and arrays until the maximum depth is reached. At the deepest level, recursion terminates with atomic values. To avoid generating only shallow structures, a recursive ratio parameter controls the probability of continuing the expansion with either an object or an array instead of producing a leaf value. This allows the generation of highly nested JSON documents while maintaining diversity in the generated structures. Each generated JSON document contains uniquely named object keys and is directly serialized to disk. By varying one parameter while fixing the others, the generator enables controlled experiments on the impact of tree depth, object width, and array length on acceptance time and memory consumption. Dataset Structure The generated JSON files follow a recursive hedge expression model. The structure is defined by the following hedge language: \[\begin{aligned}E_V &= value(1)\\E_A &= array(E_O^*)\\E_O &= object((E_O + E_A + E_V)^*)\\E_D &= document(E_O)\end{aligned}\] where: - `document` represents the root element of each JSON document.- `object` represents JSON objects whose children can recursively be objects, arrays, or values.- `array` represents JSON arrays containing objects.- `value` represents JSON leaf values.- `1` denotes the empty horizontal language (a node without children).- `*` represents repetition of child structures.- `+` represents the union of possible child types. The generated files are therefore recursive JSON trees where: - A document contains exactly one object.- An object contains zero or more elements of type object, array, or value.- An array contains zero or more objects.- Values are terminal nodes without children. This structure corresponds to the following hedge automaton: \[\begin{aligned}q_V &\leftarrow value(\epsilon)\\q_A &\leftarrow array(q_O^*)\\q_O &\leftarrow object((q_O+q_A+q_V)^*)\\q_D &\leftarrow document(q_O)\end{aligned}\] The final state is \(q_D\), meaning that generated samples represent complete JSON documents accepted by this hedge automaton. The code used to generate the dataset is: import json import os class RecursiveJsonGenerator: def __init__( self, depth=5, members_per_object=5, array_size=5, recursive_ratio=0.9 ): self.depth = depth self.members_per_object = members_per_object self.array_size = array_size self.recursive_ratio = recursive_ratio self.counter = 0 def new_key(self): self.counter += 1 return f"key_{self.counter}" # V -> value() def value(self): return "value" # O -> object(M*) def object(self, depth): if depth == 0: return self.value() obj = {} for _ in range(self.members_per_object): obj[self.new_key()] = self.member(depth-1) return obj # A -> array(O*) def array(self, depth): if depth == 0: return [] return [ self.object(depth-1) for _ in range(self.array_size) ] # M -> object | array | value def member(self, depth): if depth == 0: return self.value() # force recursion most of the time import random if random.random() < self.recursive_ratio: if random.random() < 0.5: return self.object(depth) else: return self.array(depth) else: return self.value() # D -> document(O) def document(self): self.counter = 0 return { "document": self.object(self.depth) } def generate_file( filename, depth, members, arrays ): generator = RecursiveJsonGenerator( depth, members, arrays ) data = generator.document() with open(filename,"w") as f: json.dump( data, f ) size = os.path.getsize(filename) print( filename, size, "bytes" ) if __name__ == "__main__": os.makedirs( "json_dataset", exist_ok=True )