An official website of the United States government
Locating arrays are designs used in combinatorial testing with the property that every set of d t-way interactions appears in a unique set of tests. Using a locating array to conduct fault testing ensures that faulty interactions can be located when there are d or fewer faults. Locating arrays are fairly new and few techniques have been explored for their construction. Most of the available work is limited to finding only one fault. Known general methods require a covering array of strength t+d and produce many more tests than are needed. We present Partitioned Search with Column Resampling (PSCR), a randomized computational search algorithmic framework to verify if an array is (d t)-locating by partitioning the search space to decrease the number of comparisons. If a candidate array is not locating, random resampling is performed until a locating array is constructed or an iteration limit is reached. Results are compared against known locating array constructions from covering arrays of higher strength and against published results of mixed level locating arrays for parameters of real-world systems. The use of PSCR to build larger locating arrays from a variety of ingredient arrays is explored.
more »
« less
Mixed-Level Covering, Locating, and Detecting Arrays via Cyclotomy
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
- Award ID(s):
- 1813729
- PAR ID:
- 10573267
- Editor(s):
- Hoffman, Frederick; Holliday, Sarah; Rosen, Zvi; Shahrokhi, Farhad; Wierman, John
- Publisher / Repository:
- Springer
- Date Published:
- Volume:
- 448
- Issue:
- 2194-1009
- ISSN:
- 2194-1009
- ISBN:
- 978-3-031-52968-9
- Page Range / eLocation ID:
- 37-50
- Format(s):
- Medium: X
- Location:
- Switzerland
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
SUMMARY Surface waves are critical in detecting and locating seismic sources that do not produce much high-frequency radiation. For such sources, typical approaches using body waves for detecting and locating earthquakes are less effective. Slow earthquakes and exotic seismic sources often have this seismic radiation characteristic, and array analyses of surface waves recorded on global and regional seismic networks have proven effective in recognizing such sources. Most approaches have relied on Rayleigh waves, whereas Love waves have rarely been used. Here we develop a new approach using multiscale arrays to detect and locate seismic sources with both Love and Rayleigh surface waves. The method first forms three-station subarrays and then uses three-component records of the stations to independently estimate three sets of surface wave propagation directions and centroid arrival times. The subarray estimates are then assembled to locate seismic sources and their origin times. We find that using multiple, disconnected global networks improves location accuracy and that using both types of surface waves can enhance detection sensitivity and robustness.more » « less
-
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
-
Alternative design and analysis methods for screening experiments based on locating arrays are presented. The number of runs in a locating array grows logarithmically based on the number of factors, providing efficient methods for screening complex engineered systems, especially those with large numbers of categorical factors having different numbers of levels. Our analysis method focuses on levels of factors in the identification of important main effects and two-way interactions. We demonstrate the validity of our design and analysis methods on both well-studied and synthetic data sets and investigate both statistical and combinatorial properties of locating arrays that appear to be related to their screening capability.more » « less
-
Attribute-based methods are inherently identity-less as authorization decisions are made in terms of attributes possessed by the subject rather than identity. However, anonymity against the system is not guaranteed when attribute distribution allows for the composition of a policy that few subjects can satisfy. An anonymizing array ensures that any assignment of values to t attributes that appears in the array appears at least r times. When an anonymizing array is used for subjects registered to a system and policies contain conjunctions of at most t attributes, the system cannot identify the subject using the policy to to gain authorization with greater than 1𝑟 probability. Anonymizing arrays are similar to covering arrays with higher coverage and constraints, but have an additional desired property, homogeneity, due to their application domain. In this paper, we develop constructions for anonymizing arrays and propose a post-optimization mechanism to reduce homogeneity.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
