An official website of the United States government
Determining correctness and performance for complex engineered systems necessitates testing the system to determine how its behaviour is impacted by many factors and interactions among them. Of particular concern is to determine which settings of the factors (main effects) impact the behaviour significantly. Detecting arrays for main effects are test suites that ensure that the impact of each main effect is witnessed even in the presence of d or fewer other significant main effects. Separation in detecting arrays dictates the presence of at least a specified number of such witnesses. A new parameter, corroboration, enables the fusion of levels while maintaining the presence of witnesses. Detecting arrays for main effects, having various values for the separation and corroboration, are constructed using error-correcting codes and separating hash families. The techniques are shown to yield explicit constructions with few tests for large numbers of factors.
more »
« less
This content will become publicly available on December 1, 2025
Detecting arrays for effects of multiple interacting factors
Detecting arrays provide test suites for complex engineered systems in which many factors interact. The determination of which interactions have a significant impact on system behaviour requires not only that each interaction appear in a test, but also that its effect can be distinguished from those of other significant interactions. In this paper, compact representations of detecting arrays using vectors over the finite field are developed. Covering strong separating hash families exploit linear independence over the field, while the weaker elongated covering perfect hash families permit some linear dependence. For both, probabilistic analyses are employed to establish effective upper bounds on the number of tests needed in a detecting array for a wide variety of parameters. The analyses underlie efficient algorithms for the explicit construction of detecting arrays.
more »
« less
- Award ID(s):
- 1813729
- PAR ID:
- 10573246
- Publisher / Repository:
- Elsevier
- Date Published:
- Journal Name:
- Information and Computation
- Volume:
- 301
- Issue:
- PB
- ISSN:
- 0890-5401
- Page Range / eLocation ID:
- 105202
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
By exploiting symmetries of finite fields, covering perfect hash families provide a succinct representation for covering arrays of index one. For certain parameters, this connection has led to both the best current asymptotic existence results and the best known efficient construction algorithms for covering arrays. The connection generalizes in a straightforward manner to arrays in which every t-way interaction is covered λ > 1 times, i.e., to covering arrays of index more than one. Using this framework, we focus on easily computed, explicit upper bounds on numbers of rows for various parameters with higher index.more » « less
-
Hoffman, Frederick; Holliday, Sarah; Rosen, Zvi; Shahrokhi, Farhad; Wierman, John (Ed.)For a finite field of order.q, and.v a divisor of.q − 1, additive translates of a cyclotomic vector yield a.q × q cyclotomic array on.v symbols. For every positive integer.t, for certain.q sufficiently large with respect to.v, such a cyclotomic array is always a covering array of strength.t. Asymptotically such arrays have far too many rows to be competitive with certain other covering array constructions. Nevertheless, for small values of .t , this cyclotomic method produces smallest known covering arrays for numerous parameters suitable for practical application. This paper extends these ideas and shows that cyclotomy can produce covering arrays of higher index, and locating and detecting arrays with large separation. Computational results also demonstrate that certain cyclotomic arrays for the same order.q but different values of .v can be juxtaposed to produce mixed-level covering, locating, and detecting arrays.more » « less
-
Hashing is a fundamental operation in database management, playing a key role in the implementation of numerous core database data structures and algorithms. Traditional hash functions aim to mimic a function that maps a key to a random value, which can result in collisions, where multiple keys are mapped to the same value. There are many well-known schemes like chaining, probing, and cuckoo hashing to handle collisions. In this work, we aim to study if using learned models instead of traditional hash functions can reduce collisions and whether such a reduction translates to improved performance, particularly for indexing and joins. We show that learned models reduce collisions in some cases, which depend on how the data is distributed. To evaluate the effectiveness of learned models as hash function, we test them with bucket chaining, linear probing, and cuckoo hash tables. We find that learned models can (1) yield a 1.4x lower probe latency, and (2) reduce the non-partitioned hash join runtime with 28% over the next best baseline for certain datasets. On the other hand, if the data distribution is not suitable, we either do not see gains or see worse performance. In summary, we find that learned models can indeed outperform hash functions, but only for certain data distributions.more » « less
-
Hash tables are a ubiquitous class of dictionary data structures. However, standard hash table implementations do not translate well into the external memory model, because they do not incorporate locality for insertions. Iacono and Pătraşu established an update/query tradeoff curve for external-hash tables: a hash table that performs insertions in O(λ/B) amortized IOs requires Ω(logλ N) expected IOs for queries, where N is the number of items that can be stored in the data structure, B is the size of a memory transfer, M is the size of memory, and λ is a tuning parameter. They provide a complicated hashing data structure, which we call the IP hash table, that meets this curve for λ that is Ω(loglogM +logM N). In this paper, we present a simpler external-memory hash table, the Bundle of Arrays Hash Table (BOA), that is optimal for a narrower range of λ. The simplicity of BOAs allows them to be readily modified to achieve the following results: A new external-memory data structure, the Bundle of Trees Hash Table (BOT), that matches the performance of the IP hash table, while retaining some of the simplicity of the BOAs. The Cache-Oblivious Bundle of Trees Hash Table (COBOT), the first cache-oblivious hash table. This data structure matches the optimality of BOTs and IP hash tables over the same range of λ.more » « less
