Search papers, labs, and topics across Lattice.
This paper develops a probabilistic framework for predicting the completion times of five distinct search strategies in hierarchical distributed search systems, ranging from sequential to full-tree parallelism. By modeling node scan times and layer times using statistical methods, the authors provide a priori performance predictions that are validated against Monte Carlo simulations. The findings reveal that while full-tree parallelism is theoretically superior, synchronization overhead can diminish the expected performance benefits in practice, highlighting the importance of considering operational constraints in parallel search strategies.
A probabilistic framework reveals that synchronization overhead can negate the expected advantages of full-tree parallelism in distributed search systems.
Hierarchical distributed search, locating a data pattern, or signature, across a tree-structured collection of files, underlies distributed index traversal, deep packet inspection and sequence alignment. A practitioner must decide how much parallelism to employ: scan each layer sequentially, fan out within subtrees, or launch the whole tree at once. Existing analyses answer this only partially: they characterize every node by the statistics of a signature-holding file and, for multi-signature files, need quantities revealed only at run time. We develop a probabilistic framework predicting the completion time of five search strategies, spanning sequential to full-tree parallelism, before any file is read. Node scan times are modeled as a mixture over signature presence, layer times as order statistics, and parallel subtree scans by extreme-value arguments; when signature counts are known, occupancy under capacity constraints is treated by generating functions. Each performance formula carries an exactness label: exact (or exact-in-regime), plug-in, asymptotic or bound, with each approximation quantified against Monte Carlo simulation and its regime identified. A multicore prototype reproduces the coarse separation between full-tree, layer- and subtree-level parallelism, but shows that synchronization overhead can erase the predicted separation between close strategies. The framework delivers a priori completion-time predictions with explicit accuracy regimes and negligible computational cost, the design example evaluated in under a millisecond; these timing models can support subsequent resource-cost optimization.
