Faster optimal univariate microaggregation
Authors: Felix I. Stamm
Michael T Schaub
Venue: Accepted by TMLR ()

Abstract: Microaggregation is a method to coarsen a dataset, by optimally clustering data points in groups of at least k points, thereby providing a $k$-anonymity type disclosure guarantee for each point in the dataset. Previous algorithms for univariate microaggregation had a $O(kn)$ time complexity. By rephrasing microaggregation as an instance of the concave least weight subsequence problem, in this work we provide improved algorithms that provide an optimal univariate microaggregation on sorted data in $O(n)$ time and space. We further show that our algorithms work not only for sum of squares cost functions, as typically considered, but seamlessly extend to many other cost functions used for univariate microaggregation tasks. In experiments we show that the presented algorithms lead to performance improvements on real hardware.

Published in Transactions on Machine Learning Research (10/2024)
Faster Optimal Univariate Microgaggregation
Felix I. Stamm RWTH Aochen University Germany
felia. saressttaamanslll.uuuuaaaaeee
Michael T. Schaub RWTH Aachen University Germany
schaub@cs.ruth-ccce
Reviewed on OpenReview: https: // openreview. net/ met/ forum? id- s51EUtyVly
Abstract
Microaggregation is method to coarsen a data set, by optimally clustering data points in groups of at least & points, thereby providing a k-anonymity type disclosure guarantee for each point in the data set. Previous algorithms for univariate microaggregation had a O(kn) time complexity. By rephrasing microaggregation as an instance the concave least weight subsequence problem, in this work we provide improved algorithms that provide an optimal univariate microaggregation on sorted data in (nn) time and space. We further show that our algorithms work not only for sum of squares cost functions, typically considered, but seamlessly extend to many other cost functions used for univariate microaggregation tasks. In experiments we show that the presented algorithms lead to performance improvements on real hardware.
1 Introduction
Public data, released from companies public entities, are important resource for data science research. Such data be used to provide novel types of services to socicty and provide essential mechanism for holding public or private entities accountable. Yet, the benefits of publicly released data have to be carefully traded off against other fundamental interest such as privacy concerns of affected people (Aggarwal & Yu 2008). common practical solution to circumvent these problems thus to reduce the resolution of the collected raw data, e.g., via spatial or temporal aggregation, which leads to a coarse-grained summary the initial data.
Microaggrogation Defays & Anwar 1998 Samarati 2001 Domingo-Farrer & Matco-Sanzi 2002 Domingo- Ferrer & Torra 2005) method that aims to provide adaptive optimal aggregation that remains informative, while providing certain guaranteed level of privacy. Specifically, in microaggregation we aim to always group at least & data items together onto a common representation. For instance, for vectorial data, we may map data points to their centroid values, while ensuring a cluster size of at least & points. The found centroid values of the clusters may thus be released and used as aggregated representation of the original data. Clearly, for the aggregated data remain useful for further analysis, it should remain closcly aligned with seek
the original data according to some metric relevant for the lask at hand. Hence, in microaggregation to minimize distortion metric of the aggregated data, while respecting the minimal group size constraint. This minimal group-size constraint (at least l data-items per group), which ensures a guaranteed minimal level of "privacy" within each cluster, is a major difference to standard clustering procedures such as k-means, which simply aim to obtain a low-dimensional representation of the observed data in terms of clusters.
Microggregation tasks are usually formulated as discrete optimization problems, where low costs indicate high similarity among the data items in each cluster. Similar to many other clustering problems, microaggrogation is in general NP-hard problem (see Oganian & Domingo-Ferres (000]) appendix B.1 A specifie form

---

Published in Transactions on Machine Learning Research (10/2024)
microaggregation
Age
Sick
Age
Sick
18
Yes
20
Yes
22
No
20
No
31
No
32
No
33
Yes
32
Yes
Raw data
Released data
Figure 1: Example application of univariate microaggregation to a loy medical data set. Left we have the original data containing quasi identifying information such as age and sensitive information such as health status. In the anonymized data an attacker interested the health status of an individual and equipped with knowledge about the age of an individual can no longer infer the health status with certainty. To achieve such an anonymization, potentially identifying attributes such age are aggregated. The task of finding such an aggregation while minimizing the distortion of the data is called univariate micronggregation. In this work, we are concerned with efficient algorithms to solve univariate microaggregation for various kinds of distortion metrics/ cests cost. functions.
of microaggregation that remains efficiently solvable, however, is univariate microaggregation (UM), in which the data points { to be aggregated are (real-valued) scalars. This is the focus of our work here.
Despite its relative simplicity, univariate micro-aggregation is useful primitive in number of problems. A concrete example the anonymization of degree sequences of graphs (Casas-Roma et al. 2017). Further, univariate microaggregation can also be used to provide heuristic solutions to microaggregation tasks in higher dimensions with the help of projections (Domingo-Ferres & Mateo-Sanz] 2002). In this work we consider the univariate microaggregation problem under wide range of cost functions, including the typically considered sum-of-squares error (SSE) based on the (squared) & norm, the l norm, the & norm and round- up cost error lypes.
Contributions Our main contributions are as follows (see Figure
2 for visual representation).
We show that for "ordered minimizable" cost functions UM can be solved in O(n"), improving previous results with exponential runtime. We achiove this by rephrasing UM as a least weight
subsequence problem (Wilber 1988 Wu 1991).
We show that for ordered minimizable cost functions, which in addition have a "splitting is beneficial" property, this can be improved to Okk)). This includes many popular cost functios based on the & norm (sum of absolute errors), l norm (sum of squared errors), to (maximal error) norm, and round up/down cost functions.
Finally, we show that for ordered minimizable cost functions which are concave, algorithms with ((n) time and space are possible. These findings apply above mentioned examples of lp norm-basod cost functions.
In our presentation we focus on three key conceptual ideas: "ordered minimizable", "splitting is beneficial", and concave costs. While these concepts already implicitly present in the literature, they typically not made explicit, which make it difficult to relate the underlying algorithmic ideas to each other. Making these concepts explicit, enables us to unfold a natural problem hicrarchy within the associated univariate microaggregation formulations, which leads us to the design of two algorithms that use all three concepts: the simple+ algorithm and the staggered algorithm. These algorithms have faster runtime compared with previous algorithms for the UM task. Lastly, we provide several practical improvements specific to UM that allow for (i) algorithms that run empirically faster in practice and (ii) substantially decreased impact of floating point errors the resulting clustering. Overall, work thus enables to robustly compute
2

---

Published in Transactions on Machine Learning Research (10/2024)
Now: O(kn)
This work Simple+
Ordered +
Splitting
Prev.: O(kn)
Minimizable
[O(kn), fast for small k] Staggered Algorithm
Now: O(n²)
Now: O(n)
Prev.: exp. +concave
Prev.: O(kn)
[O(n), fast for large k]
Figure 2: Complexity of UM on sorted data for different classes of cost functions. For ordered minimizable cost functions univariate micronggregation can be solved in O(n²). If additionall splitting is beneficial, then one can actually solve UM in O(k)) while for concave cost functions UM can be solved in O(n). For cost functions that have both properties we provide the Simple- and the Staggered algorithm which have faster empirical runtime without sacrificing worst case bounds.
optimal UM-clusterings for various cost functions and large values of and k. An implementation of the presented ideas is available at https:///itthb.. .cmm///elll22///mc/coggggg. and the code can also be found at htttp:://dii..oo 1111110..2222oooll/ 20t. 10459327
Outline In Section 2 we first outline definitions associated with UM and the related least weight subsequence (LWSS) problem. In Section 3 we then show that for ordered minimizable cost. functions, we can reformulate CM as LWSS problem which allows for O(n²) algorithms. For cost functions with the splitting is beneficial property, this runtime complexity can be improved to Okn). For concave cost functions this can be futher improved to On)). Closing Section we introduce simpler and empirically faster O(n) algorithm for UM. In Section 4 present considerations for running UM on real hardware. First, we present two strategies to avoid issues arising from finite float precision. Second, we illustrate small algorithmic trick to use fewer instructions when computing the cluster cost, which is the main computation carried out within UM. We verify that the presented theoretical considerations lead to significant empirical performance improvements in Section
1.1 Related Work
The question of how to publicly release data, while retaining certain levels of privacy, has bocome incrcasingly imporlant in recent years. Privacy preservation for data sets is most relevant if data entries contain both public as well as sensitive private information. Note that what information is considered public and private can depend on the application sccnario. For instance, we may have tabular data, where each row contains public information such as name or age, conjunction with private information such as medical diagnoses. In this case, an important objective to design a surrogate data set, such that it virtually impossible to use public information to deduce private information about an individual.
The public attributes of database usually be split into identifiers and quasi-identiffers. To privacy- harden database it is typically insufficient to merely remove identifiers such as name or social security number. It can often remain possible to identify an individual in the data set by a combination of quasi- identifiers (Rocher et al.] 2019). e.g., there is only one 30 year old female in the data. Thus other privacy protection measures need to be employed.
To combat the leakage of sensitive information, different privacy concepts such as I-diversity (Machanava- lihala et al., 2007), t-closeness Li et al.) 2007), and the popular k-anonymity (Samarati & Sweeney] 1998; Samarati 2001 Sweeney 2002) have been proposed. The latter is the privacy concept with in this work. If a data set is k-anonymous, it is not possible to use any combination of quasi-identiffers to narrow down the set of individuals described by those quasi-identifiers to less than k individuals. Because 1 other rows indistinguishable by quasi-identifiers alone, it remains impossible to
are concerned
there will always be deduce which data item corresponds to a specific identity, no matter how much knowledge about the quasi- identifiers of an individual available. Unfortunately, data sets are usually not inherently k-anonymous but the released data needs to be altered to become k-anonymous distorting the statistics of the released data.
3

---

Published in Transactions on Machine Learning Research (10/2024)
Domingo-Ferrer & Torra 2005) was proposed as method to make a data set k-anonymous. Therefore data entries are grouped into groups of size at least k, and the quasi-identifiers of entries are replaced with their group-centroid values. To uphold the utility of the released data, the grouping is conducted by minimizing a distortion metric subject to minimal group size constraint. Solving microaggregation with more than one variable, so called multivariate microaggrogation, is known to be NP-hard for the sum-of-squares cost function (Oganian & Domingo-Perrer/ 2001), a popular distortion metric. To perform multivariate microaggregation in practice, several algorithms have been proposed. Some of these alogorithms come with approximation guarantees, while others are simply heuristics. We refer to Yan et al. (002) for many references to algorithms for multivariate microaggregation.
Microaggregation Feemingo-Ferrer & Mateo-Sanz 2002 Defays & Anwar 1998
Microaggregation with only one variable, so called univariate microaggregation, is known to be solvable in polynomial time. More precisely, (kk) for the sum-of-squares cost function (Hansen & Mukherjee 2003) by constructing graph and solving a shortest path problem on this graph. Algorithms which solve univariale micronggregation may also be used to solve multivariate microaggregation problems. Recently, other cost functions besides SSE have been used for univariate microaggregation tasks such as degree-sequence anonymisation [Casas-Rooni et al. 2017
We remark that the term univariate microaggregation is also used in the literature to describe a microag- gregation problem of ordered high dimensional data: In that scenario we are provided with data vectors 2; E Rd, with 2 2 and an extrinsically defined total order of the points, which must be respected when creating clusters. Hence, any cluster that contains the points 2; and Ij must also contain all points greater than Ia and smaller than 2j according to the provided ordering. While some of the ideas develop here may be extended to this scenario, this is in general not trivial task and beyond the scope of this work.
2 Problem Formulation and Preliminaries
In univariate microaggregation (UM) we consider set of scalar data points x; R for I,..., , n. To keep the treatment general we allow for repeated elements I₁, i.e. we consider our universe Q f[11, ((........ ................................ In to be a multi-set of points. The goal of UM can now be formulated as follows.
Definition 1 (Univariate Microaggregalion problem). Given mulli-sel of scalurs S2 [II,.....
. Fn find a non-emply partition of the points into clusters Xj, such that each cluster has size at least k and a total additive cost function TC = E, C(X;) is minimized, where C denotes cost function that measures the distortion within each cluster.
Formally, we look for a partition, i.c., a split of the multi-set Q into nonempty multi-sets X, * 0, such that Uh_ X; = Ω. To avoid confusion, in this work the union of two multi-sets an additive union, i.e., the multiplicities of the elements add up when forming the union of two multi-sets. Notice, that there might be multiple partitions minimizing the total cost even if all x; are unique. This is usually not problem we are typically interested in finding any partition minimizing the total cost.
approach, neglecting possible structure in the cost function C' needs at least exponential time, as all possible partitions have to be assessed. However, two important observations have been employed in the literature to lower this complexity. First, for many cost functions can be shown that a minimal cost partition has no interleaved clusters (see Corollary or Domingo- Ferrer & Mateo-Sanz) (2002) for the special case of SSE). This substantially restricts the search space that needs be explored in order to find optimal solution, as it implies that only pairwise-ordered clusterings need to be considered. From now we thus assume that data points z; sorted in ascending order, iee. < j I; S xz. For given cost function C, this allows us to denote by (i..)) == C(f I }),, the cost of a cluster with starting point ri+1 and endpoint xz. Second, for many cost functions, there a always exist an optimal cluster assignment in which no cluster has size larger than 24- 1, i.., it is never detrimental to split clusters of size at least 2k into smaller clusters (sec eq. [ or Domingo-Feen Ferrer & Matco-Sanz (2002) for the special case of SSE). This also reduces the size of the search space, as there no need to check possible clusterings containing clusters of size greater 2k: 1.
A
4

---

Published in Transactions on Machine Learning Research (10/2024)
Previously, these observations were used to solve univariate micoraggregation for the SSE cost function sorted data in (kk) time (Hansen & Mukherjee 2003; Mortazavij 2020). In the following we will exploit the fact that many popular cost functions are concave cost functions, which can be used to create even faster algorithms. For these concave cost functions it is possible to achieve ((n) runtime algorithms for the UM problem on sorted data by rephrasing UM as a least weight subsequence problem.
2.1 The Least-Weight Subsequence Problem
As we will see in the next sections, univariate micronggregation can actually be phrased such that established algorithms which solve the least-weight subsequence problem can be applied to UM. Hence, we briefly recall the relevant aspects of the least-weight subsequence problem
Definition 2 (Least weight subsequence problem (Wilber 1988) ). Given an integer n and a cost function
() find an integer 2 1 and a sequence of integers = lo < 1 .... < 1--1 < ly = n such that the total cost. TC E (41) is minimized.
2.1.1 A Standard Algorithm (Wilber 1988)
To gain some intuition about how to solve the leigt-weight subsequence problem, we first outline an algorithm with an Onn²) time, ((n) memory requirement. To this end we introduce the auxiliary variables maj, which is the sum of the cost obtained after solving the LWSS problem for the points x4... plus the cost of Ctt,j) = C(f ,T,)), R). We call my the conditional minimal cost. More specifically, maj := C) is simply the cost considering the first ý points to be in a single cluster. The remaining conditional minimal costs are then recursively defined as my == minge my + C(i.j). We notice that mintes my is the minimal total cost required to solve the leagt-weight. subsoquence problem the points 21 .., and so my can be interpreted as the sum of the costs of (i) assigning the first i points optimally and (ii) assigning the points (3itI...., B to a single cluster.
To efficiently compute all mij we make use of a lookup array A which we fill with the relevant my entries as follows: We first compute mo1 and store it in array A at position 1. Next, we compute the conditional minimal costs mg2 and m12- To compute m12 we read the entry mg1 from our lookup array at position 1. We store the minimum of mg2 and m22 in array A at position two. We can continue in the same way iteratively. In each iteration we increase j by one and compute all the conditional minimal costs my with < Each my requires the value min my, which we end of cach such itcration we store min, maj in our array A at position j such that it is available for further computations. The algorithm terminates once we have found min; Min which corresponds to the minimal total cost. Overall, this takes (n²) time if we can compute the cost function in 0(1).
read from array A at position i. At the
In univariate microaggregation we are usually more interested in a minimal cost clustoring rather than the minimal cost itself. This can be achieved by slight adaptation of the above algorithm. Whenever we compute min, Myj also store the index i = arg min, my of the minimum in a linear array Aind at position j. The full pseudo code for this algorithm can be found in Alg, 2 The result of this standard algorithm implicitly holds the information about a minimal cost clustering which can be obtained by backtracking in (m)). Starting with j j=m n we consider min = arg min; mij which we can read from our array Aind at position j. All points with index with imin < < belong to one cluster in the optimal costs clustering. If imin > 0 we repeat the same process with j = min to obtain the next cluster. Full pscudo code of this backtracking procodure is provided in Alg. in the appendix.
2.1.2 Algorithms for Concave Cost Functions
More efficient algorithms than the standard algorithm outlined above are known for the concave least weight subsequence problem. The problem is called concave if the cost function C' satisfies for all 0 < a <<<<<<
d < n
C(a, c) + C(b, d) s C(a, d) + C(b,c).
(1)
The above constraint, is sometimes called "quadrangle incquality", If a cost function fulfills this requirement
it is called concave Wilber (1888) Galil & Park (990).
5

---

Published in Transactions on Machine Learning Research (10/2024)
If we consider non negative cost functions (ie. VxC(X) 0) with the property that one-element cluster has no cost (C(i, i 1) 0), we can derive few interesting implications about concave cost functions. The first observation is, that wide is worse. Mathematically this means that for a < b b<c
C(a, b) S C(a,c)
C(b, c) S C(a, c).
In simple words, this means that if we widen a cluster by adding more points to the left or to the right the cost does not decrease. A similar consequence concavity is that splitting beneficial, i.e. for all a <
C(a, + C(b, S C(a,c).
(2)
Note that the above equation is effectively an opposite of the triangle inequality (which would hold for so-called convex cost functions).
Most important for solving least weight subsequence problems is the consequence that the associated matrix C' with entries C.2 C(i,j) is Monge matriz (where for notational convenience we index the rows starting from zero and the columns starting from 1). Most relevant for our purposes is that Monge matrices and their transpose are totally monotone (Burkard et al. 1996), i.e., it holds for each 2 2 submatrix
(x 7 8)
a B
that y implies that < 3 and, similarly, we have 7 = constant value to column of totally monotone matrix, the resulting matrix is again totally monotone. This implies that the transposed conditional minimal cost matrix M with entries M,j maj is totally monotone, as it is obtained from the transposed cost matrix C (which is Monge) by adding constant values (min, ma) to the columns. Finding all minima within the rows implicitly defined totally monotone matrices of shape n x m (n S m) is possible in ((m) using the SMAWK algorithm (Aggarwal et al. 1987)
S B. It is easy to see that if we add a
Using the SMAWK algorithm, dynamic programming (Wilber 1988 Galil & Park 1990) allows us solve the concave least weight subsequence problem in O(n) if the concave cost. function C can be computed in
((1) time using (n) time for preprocessing. While the works (Wilber 1988
Galil & Park 1990) focus
concave cost functions C, we notice that the presented algorithms in (Wilber 1988 Galil & Park 1990) will also work if the corresponding transposed cluster cost matrix M is only lotally monolone. As we will see in the next chapter, univariate microaggregation for concave cost functions can be phrased as a least weight subsequence problem with an non-concave adapted cost function Cadapt- The corresponding transposed cluster cost matrix MT is nonetheless totally monotone which allows for the algorithms from (Wilber 1988: Galil & Park 1990) to be applied to univariate microaggregation.
3 Faster Univariate Microaggregation
In the following we present what properties of the cost function can be used to efficiently solve the univariate microaggregation problem. We first reformulate UM a least weight subsequence problem (LWSS) which allows for O(r²) algorithms. We call cost functions which allow this reformulation ordered mánimiiaale. If cost functions additionally also have the splitting is beneficial property, O(kn) algorithms are possible. For the very common type of concave cost functions, we show that UM can be solved in (()). Lastly, wo present an O(n) algorithm, the staggered algorithm, which shows faster empirical running for the concave UM problem compared to more generic O(n) LWSS algorithms presented (Wilber 1988 Galil & Park 1990).
3.1 Reformulating Univariate Microaggregation as a Least Weight Subsequence Problem
When comparing UM and LWSS, the most apparent issue is, that in the LWSS problem the values are inherently ordered while for UM no such inherent order is apparent for all cost functions. We will thus consider properties of cost. functions that imply an inherent order. We will now characterize those cost
6

---

Published in Transactions on Machine Learning Research (10/2024)
functions that allow reformulation of the univariate micronggregation problem as a least weight subsequence problem. Parts of the below work is inspired by the treatment of SSE by Domingo-Ferrer & Mateo -anz (2002).
Definition 3 (Pairwise ordered sets). We call two (malti-)sete A and B pairwise ordered iff all elements in one set are smaller or equal than those in the other, i.e. VaEA.EB a I b or VacA,beBB b S a. We call a partilion pairwise ordered if all pairs of mulli-sels in the partálion are pairwise ordered.
Equipped with this definition we can characterize those cost functions whose UM problem can be reformulated as least weight subsequence problem.
Definition 4 (Ordered minimizable). We call total cost TC ordered minimizable it is sufficient to consider only pairwise ordered partitions when minimizing the total cost TC over all relevan J partitions of the universe Ω
To grasp the importance of definition 4 lets consider the case of minimizing an ordered minimizable total cost for a bipartition. If there are n elements there are n pairwise ordered partitions splitting the data in two parts, but there are 2n 2 partitions in total. So being able to only check all pairwise ordered partitions makes huge computational difference.
While Definition probably the least restrictive definition, most widcly used cost functions fulfill the more restrictive following definition which mixes both the UM and k-means restrictions.
Definition 5 (4-partition ordered minimizable). A total cost function TC is q-partition ordered minimizablle if for all partitions P = X Xy with multi-sets of cordinalities Sp == k|X,1 for i E {l,....q t H there is a pairwise ordered partition pr consisting of multi-set with cardinalities Sp = Sp that fulfills TC(P') S TC()).
Theorem 6. If lotal cost function is 2-portition ordered minimizable, then it is ordered minimizable.
In the proof of Theorem we show that if a cost function is 2-partition ordered minimizable it is q-partition ordered minimizable for all q. This implies that it ordered minimizable. For the full proof see Ap- pendix B.5.1 in the appendix. Using Thcorem B can be shown that the following cost functions are ordered minimizable.
Corollary 7. The lotal costs TC C associaled to following cost functions C are ordered minimizz able:
Sum of Squares Error C(X) = SSE(X) = -x -X)=
Sum of Absolute Error C(X) SAE(X) = |x -M))), where M is the median of X
2o Marimum distance C(X) = (X) maxxEx 10 - -X), where X (max(X) + min min(X)))2
20
Round up error C(X) Cx(X)= = Exex |r max(X)l
Round down error C(X) = C((X) = Exex |x min(X)
The sum of absolute error cost has been previously proposed under the name absolute deviation from median (ADM) (Kabir & Wang 2011). For the scenario in which all values z; are integers, oum-of-squares distortion metric with rounded mean was also proposed (Mortazavi 2020) to be able to perform all operations on integers only.
For the proof of Corollary 7 see Appendices B.5.3 to B.5.6
When dealing with any ordered minimizable cost function, we thus can sort the input data either in ascending or descending order (ascending is usually preferred for numerical reasons). Depending on the data, sorting can be done in On log m) or O(n) (e.g. radix-sort on small integers). Currently, sorting is part of any practical algorithm to solve UM exactly and we thus consider the time complexity of all algorithms on sorted data, thereby neglecting the potential additional cost of logn.
For UM the relevant partitions are those which respect the minimum cluster constraint. For k-means the relevant. partitions are those of size

---

Published in Transactions on Machine Learning Research (10/2024)
If cost functions are 1) ordered minimizable, and 2) can be computed in O(1) based ((n) preprocessed data, we solve UM in O(n²) time and ((n) space. This can be done by adapting the cost function of the classic algorithm for LWSS problems such that large cluster costs are returned if the cluster size is smaller than
VAL j-ick h. C(i.j) elsc.
Cadapt (1,j)=
(3)
Here VAL is arbitrary large enough number, such that the cluster cost C is always smaller than VAL, Le., C(i,j) < VAL for all valid choices i < j. The following lemma ensures that we use this adaptation for all previously considered cost functions.
Lemma 8. The cost functions introduced in corollary 7 can be computed in O(1) using O(n) time for preprocessing and consuming no more than O(n) additional memory.
For the proof of Lemma Appendix
B.3
Many cost functions are even more structured, which allows faster algorithms as we will see in the next subsection.
3.2 Univariate Microaggregation for Cost Functions where Splitting is Beneficial
If the ordered minimizable cost function also has the splitting is beneficial property (i.e., eq. holds), we can improve upon the O(n²) time complexity for the classical algorithm. The main insight is that we do not need to consider clusters that contain less than or more than 2k - 1 points. We can "forbid" these clusterings by adapting the normal cluster cost. For too small/too large clusters we return large costs which ensure the forbidden assignments are never selected. Thus adapt any cost function with the splilting is beneficial property
VAL j-ick k,
Cadapt (i, =
VAL j-i2 iz 2k, C(i,))
(4)
clsc.
Similar to LWSS we can define a matrix M with entries M., = min my + Cadape (i.j). If we consider the structure of the M matrix (see colors in Figure 3), we find that there only k entries per column that need to be considered (green entries in Figure 3h. In particular, when computing the minimum value in each column of the matrix M only entries M, with j 2k + < iis - k are necessary to be computed to find the minima of column j. This allows a complexity improvement of the classic algorithm from O(n²) to Okn)). We conclude this subsection by noting the introduced considerations are applicable to the presented cost functions.
Corollary 9. All the costs presented in Corollary have the splitting is beneficial property-
This is true as they are concave (see next subsection, Lemma 10
they have C 2 0 and C(i,i
3.3 Univariate Microaggregation for Concave Cost Functions
Besides the classical algorithm used to solve least weight subsequence problems, more advanced algo- rithms Willer 1988 Galil & Park 1990) are available to solve concave least weight subsequence problems in (n)). We observe that those algorithms will also work if the associated cluster cost matrix M" is only totally monotone. The previous definition of Cadapt. (eq. (3) needs be slightly modified such that the matrix R is totally monotone for these algorithms to be applicable.
VAL(i) j-ick h C(i,j) else.
Cadape
(5)
8

---

Published in Transactions on Machine Learning Research (10/2024)
We again choose the large costs VAL(I) large enough such that C(i,)) < VAL(I) for any 1 (1 ك S n) and any valid j. Further, we require VAT.(1) < VAT(m)) for 1 < m to ensure total monotonicity of the transposed cluster cost matrix M
If our cost function is concave this definition of the adapted cost Cadapt ensures that, the transposed cluster cost matrix M is totally monotone (see appendix for a proof, visualization of such a matrix is provided Figure if we assume the orange entries are also green). For cost functions C' in that can be evaluated in O(1) function and solve this problem using dynamic
time (for (n)) preprocessed data) can use Cadapt programming algorithms, e.g,, via the algorithm by Wilber (1988), or algorithm proposed by Galil &
Park 1990), to obtain a solution for univariate microaggregation on sorted input in O(n) time and space.
For the special case of the sum of squares cost, it has been previously shown, that the cost is concave (Grön- lund et al.) 2018 Wu 1991) and can be computed in O(1) (using O(n) time and space for preprocessing) using a cumulative sum approach. These results have been used to speed up the 1D k-means problem (Grøn- lund al. 2018), but have not yet been used to solve univariate microaggregation tasks. Let assert. that all of the considered cost functions in Corollary are indeed concave:
Lemma 10. The cost functions from Corollary
concave.
For the proof of Lemma 10 we refer to the appendix Appendix B.4
Putting together Corollary Lemmn and Lemma. 10 we obtain the following result:
Theorem 11. On sorted data, we can compute optimal univariate microaggregation in ((n) time and space for the cost functions introduced in Corollary 7
Naturally, Theorem extends to unsorted data if we pay at most an additional O(n n) cost for sorting,
3.4 Univariate Microaggregation for Concave Costs where Splitting is Beneficial
If cost. function is concave and splitting is beneficial we can combine restricting the cluster size and preserving total monotonicity to arrive at the following adapted cost
VAL(i) j-i -i< < k
(t
VAL(-i)
j j- 2 2k
(6)
C(i.g) else
As before VAL(() should be large enough such that C(i,j) VAL(() for all valid i, j, but this time not only for positivel, I, but also for negative I with values beteen -n I We require again that VAL(I) < VAL(m) for / < m to ensure total monotonicity of the transposed cluster cost matrix M.. We proove that for this definition of the adapted cost Cadapt the transposed cluster cost matrix M" is totally monotone in appendix Appendix B.2.2 The structure of the cluster cost matrix correspond to this definition of Cadapt is displayed in Figure
When a cost function has both the splitting is beneficial property and is concave, possible to significantly decrease the runtime of the classical algorithm introduced in Section 3.2 To this end is instrumental to observe that in totally monotone matrices, the positions of the minima of the rows non decreasing (see Alg. for pseudo-code). Although this does not. provide an asymptotic runtime improvement, it greatly decreases empirical runtime for larger k (see Figure
By incorporating the cluster size constraints, it is moreover possible to improve the generic algorithms for least weight subsequence problems (Wilber) 1988: Galil & Park 1990) for concave cost. functions with the splitting beneficial property. We present an algorithm for this problem in the next subscction.
3.5 The Staggered Algorithm
When solving UM, the algorithm by Wilber Wilber 1988 and the algorithm by Galil and Park (Gali) & Park 1990) are both generic dynamic programming algorithms that work with any kind of ordered minimizable concave cost. function. They achieve the linear running time by repeatedly calling the SMAWK
9

---

Published in Transactions on Machine Learning Research (10/2024)
algorithm Aggarwal al. 1987 to compute the minima of rows of submatrices of the totally monotone matrix M These algorithm only use the concavity and are oblivious to the restriction on the cluster size and the resulting structure of the M matrix (compare green entries in Figure 3 In contrast, we have the (kk) algorithm (Domingo-Feres Ferreer et al.) 2008) or the adapted classical algorithm (Section 3.2 which are unaware of the concavity of the cost function and use the restrictions on cluster sizes achieve speed. By using both the restrictions on the cluster sizes and the concavity of the cost function we can obtain an algorithm that empirically runs faster than the other O(n) algorithm on UM tasks, and the asymptotic runtime is still ((n). We present the pseudo code for one such algorithm, "the staggered algorithm", in Alg. 1 The main idea of the staggered algorithm is to apply the SMAWK algorithm to matrices along the diagonals that correspond to valid cluster assignments (see Figure 3 for a visualization of this idea). For UM lasks, the algorithm is empirically faster as fewer calls of Cadape are wasted on combinations of i, which are forbidden by cluster size constraints. Lastly, the staggered algorithm is conceptually simpler than the other two ((n) algorithms which employ guessing and recovery strategy to cope with unavailable entries mini<i myj- For the staggered algorithm, such guessing needs to be employed, all necessary entries are available when making calls to the SMAWK algorithm.
This algorithm has space and runtime complexity of ( for cost functions that can be computed in O(1) using (nn) preprocessing. To see this, not that any call to the SMAWK algorithm is O(k) and there at most [ calls to the SMAWK algorithm. This means that all the calls to the SMAWK algorithm are at most Onn).
sorted array minimum size k, cost function calculator C Output: array implictly representing the optimal univariate micronggregation of let n length(v)
Input:
if n S.S2 2k then
return all zeros array of length
C.do piloopreproccsing(v, k) SMAWK.cost. C
for i (k...., 2k 1 do
MMAWWK.MinTotalCCC = C.calc(O, i)
=
SMAWK.col. 1200___mn22..___1111111111111_11 (3k - 1., k 2k- 1)
10 if n S 3k - then
11 return
12 f, f,R= (n-33 3k + 1) divmod A:
13 for iE
f) do
14
SMAWK.co min(ik: (i+ + 1)ks 1, 2}h + 1,
15 if R then
16
1=3+f
17
SMAWK.col min(ik, n, (i 2) + 1,
18 return SMLAW..Argmi Cotal
Algorithm 1: Pseudo code for the staggered algorithm. This algorithm uses both the concavity of the cost function through the use of the SMAWK algorithm and the restrictions, that clusters are of size at least k and at most 2 - 1. When calling SMAWK.co _)ll_i_k.....l. the SMAWK algorithm is applied to compute the column minima of submatrix of the implicitly defined cost matrix M which contains columns í through j and rows & to (see boxes in Figure 3 After executing the SMAWK algorithm, the minimal total cost for cach column is stored in MonTotalCost and the row that corresponds that value is stored in ArgminTotalCoom TotalCost.
10

---

Published in Transactions on Machine Learning Research (10/2024)
7001
7802
mg3
770
1705
1706
1007
mg8
701
122
13
1014
m116
m17
m18
721
m22
122
7724
m825
m226
m27
mgg
703
m32
m33
1734
m33
m336
m33
m33
7411
m22
m44
1744
m445
m446
m47
m48
105
m22
1153
1754
7155
67156
mA57
m158
7661
M62
m63
1764
m65
m766
1767
m68
22
1173
107
11766
1077
1178
Figure 3: Visualization of how the staggered algorithm processes the cluster cost matrix M for cost. function that is concave and has the splitting is beneficial. The matrix is shown for n 8 and k = 2. Red entries correspond to clusterings which contain clusters that are to small. Orange entries correspond to entries that contain unnecessarily large clusters and green entries need to be processed to find an optimal univariate microaggregation clustering. In Alg. [ Clines 5-7 initialize moz and mag- Line 9 processes the first submatrix indicated by the square overlay columns 4 and 5. For most inputs the loop in lines 12 & 13 processes most of the matrix (here only columns 6 & 7). Lastly, potentially remaining columns are processed in line 15-17.
4 Univariate Microaggregation on real hardware
So far we have considered the mathematical foundations underlying fast UM algorithms. In practice though, the computations involved are not happening at arbitrary precision. On most current hardware, caleulations involving reals are executed with fixed width floating point numbers (e.g. 32 or 64 bits). We notice that utilizing the presented algorithms/one /csst functions can result in suboptimal clusterings, due to finite precision of these floating point numbers. We thus dedicate the next two subsections to the analysis and mitigation of errors caused by finite precision floating point numbers. At the end of the section we also highlight a real world runtime improvement possible for some of the cost functions. As a running example we will consider the sum of squares cost function, though many of the considerations carry over to other cost functions well.
The default approach of computing the SSE in 0(1) is to first precompute (in O(n)) the cumulative sums
5 = Σ xz and s (1) = Σ x
$
with s()(0)) = =022(0) = 0. Then we can compute for i <
((0))))s(0(
= s( (i)
(7)
j-i
which is constant time irrespective of the values of i and j.
4.1 Floating Point Errors During Preprocessing
When computing the cumulative sum during preprocessing, the running sum can grow and reach quantities which are no longer represented well numerically. This can lead to erroneous cluster cost being calculated which in turn may lead to suboptimal clusterings. As an example, computing the sum of squares error according to eq. (7) on the integers (i.e. the universe is Ω 10,1,2,...) }) using 64bit floats returns the wrong result. SS ES 082) 1 (which should be 2). We can do better than the simple cumulative approach, by observing that only need to consider C(i,j) with j-i < 2k - for UM. This means we don't need the full cumulative sum and can get away with sums of fewer elements.
We therefore consider partial cumulative sums which are cumulative sums which we restart every k-th time. So in preprocessing we compute the partial cumulative sums
(1) $1
Σ
31
KiS
11

---

Published in Transactions on Machine Learning Research (10/2024)
for i = k, .k.... and j(i) - 1, 1,,,+22.... 2....,8+ , k, and we set 80 0. We can do this similarly for the cumulative sums of the squared entries. Both of these preprocessing steps take ((n) time and O(n) space.
Using these partial cumulative sums, we can also compute the sum of squares error for univariate microag- gregation. Let us denole with m, = mod j the modulus m and remainder r of the integer division of by j. Then we can compute the SSE from the Si for a univariate microaggregation problem with min size k: For j j compute m,, r; = mod and my. = mod k. We now notice that for valid entrics i we have my m, as j S 2k- Lets first consider my = m,, then we compute the SSE as
SiE(i,)) = (2)
(1) (mi)r smgirs )² /0i -
2 )
In the case that my = my + 1 we compute the SSE as
) 2 /(-
SSE
s
(2)
m..k my.rr
my..r
m,kk
m
Both of these are (1) but the numbers involved in the cumulative sums much smaller which can decrease floating point representation errors. This considcration is particularly important for the case of SSE and ME both of which use cumulative suns in their computations.
4.2 Floating Point Errors when Computing the Total Cost Function
When computing the total cost function TC we are computing the sum of at least Lzx-T_ values with equal sign, thus TC is increasing in magnitude with each summand. Yet, floating point numbers have a higher absolute resolution close to zero. It would thus be numerically advantageous if we could keep the total cost TC close to zero. For cost function with the splitting beneficial property this can be achieved without increasing the runtime complexity by regularly resetting the stored TC values. Most algorithms work by first computing and storing the minimal total cluster cost TCCin == min, mig of the first q points (see Scction 2.1 for the definition of myj). Then the algorithms find the optimal clustering of the next q - p points based on the optimal clustering of those previous values up to q. We notice that TCmin (!) increases as | increases but for cost functions where splitting is beneficial we only need to know the last 2k- - total cost values, i.e., we need to know (g)in(4) for 2 | - (2k - 1) to compute the total cost TCmin (1). Thus for certain algorithms we can reduce the growth of the total cost as follows. On a high level, we subtract the smallest stored and still needed minimal total cost from the other stored and still needed minimal total cost values at regular intervals. As an example, consider the classical algorithms simple and simple+ with their pseudocode in Alg. 2 To implement the strategy, could expand the loop spanning lines 7-9 in Alg.
(continuing the loop in lines 7-9 in Alg. 2
Let imin be the lower bound of the argmin in line 8 of Alg, 2 MinNeededMinnCost = min MinCost(i]
for i E (imin + 1,...,j) j} do MinCost|ji] MinCost|ji MinNeededMMinCost
Here we subtract the still needed minimal total cost MinNeededMinnost from those MinCost values that are st.ill needed in future ilerations. The values that still needed in future iterations of the main loop are designated mostly by the lower bound imin- This lower bound differs depending whether consider the simple or simple+ algorithm. It is possible to do a similar procedure for the staggered algorithm without changing the runtime complexity of either algorithm. Using such a procedure, we can ensure that the total cost TC doesn't grow as a function of x x but remains nearly constant (in the case of himple/siplle+ or growth as a function x & in the case of the staggered algorithm. Thus for small and large n the described procedure allows us to make use of the higher absolute floating point resolution near zero.
4.3 Faster Cost Function Evaluations
As a final consideration for implementing UM on real hardware, we consider how to compute the cost function with fewer instructions. All the here presented algorithms work by computing the optimal partitions of the
12

---

Published in Transactions on Machine Learning Research (10/2024)
sorting
simple
simple+ +
galil, park
wilber
staggered
0.6
0.5
0.4
runtime [s]
0.3
0.2
0.1
0.0
10
10a
10
10
minimum group size k
Figure 4: Runtime random data of size 1 million function of minimum group size k. Colors indicato different algorithms displayed in the legend above. The time to sort the elements is included as baseline (black). Shown are mean and standard deviation over 10 repeats. As cost function, the sum-of-squares cost function as introduced in section 4.1 used. The simple dynamic program (denoted as "simple", pseudocode in Alg. 2 is representative of algorithms previously proposed (e.g. Sammingo-Ferren & Matco--San 2002). is slower than the newly proposed dynamic program (simple+,, pseudocode Alg. 2 for any minimum group size For small values of k, the (kk) dynamic programs simple and simple- are faster than the ((n) algorithms staggered, Wilber, and Galil Park. For large values of the minimum group size k 2 30 the (()) dynamic programs are faster than even the improved O(k)) program.
first elements the universe Q. Let us denote these first g elements with 0!...,, From the optimal partition of the first q points, the optimal partition of the first q 1 points of the universe can then be computed. During this process we only compare the total cost of partitions of the same set [(.... Stated differently, compare the total cost TC(Pat....)) of one partition Pap...el of the first points 2(.... with the total cost of another partition P ". of the same set O(.... g) If we are only interested in the resulting clustering and not in the actual cost of the clustering, we can minimize cost functions which require fewer operations to compute than the original cost functions. This idea is more easily understood with an example. Lets assume we want to minimize the SSE on partitions the first q elements of the universe then for two partitions Pap...g and Pk R)....) of this set,
TCsSE( (CsSE(Pai.... P((...)) S TCssE( P
Pa....e))
X2
X2
Σ
X
X
ZER [.......
XEP:
rEf rEf
XEP
ČSSE (X)
Σ
ČsSE(X)
XEP:
XEP
with
X²
ÖSSE(X)
(8)
X
Overall, we find the clustering that minimizes SSE is equivalent finding the clustering minimizing ÖSSE if only algorithms that compare clusterings of the same set [(..., We can find similar expressions
13

---

Published in Transactions on Machine Learning Research (10/2024)
0.5
0.4
runtime [s]
0.3
0.2
0.1
0.0
10
10a
10
10a
minimum group size k
Figure 5: Runtime impact of different methods to compute the cost functions. Colors indicate algorithms, linestyles indicate methods to compute the cost functions. Shown are mean and standard deviation aggre- gated over 10 runs. The colors red/blue indicate the petggered/simplees algorithm respectively (same colors as Figure The dashed lines are the default cumulative sum approach (eq. 7 the solid lines are the partial cumulative sum method introduced in section 4.1 and the dotted lines indicate the alternative cost function approach introduced in section 4.3 We see that overall for the same algorithm the alternative cost function is fastest with the default cumulative sum approach being not much slower. The partial cumulative sum approach comes with big runtime penalty.
for some cost functions, well:
(x()) = |X] max(X)
(x( = - -|x min(X)
5 Experiments
In the following we show to kinds of experiments, Firstly, we perform runtime experiments evaluate whether the theoretical considcrations made lead to performance improvements real hardware. In the second set of experiments we evaluate whether projection based approaches are a possible competitor to solve the multivariate microaggregation task.
5.1 Runtime Experiments
We compare the algorithms by Galil and Park, Wilbers algorithm, and two versions of simple dynamic program, one which does only use the restrictions on cluster sizes (simple) and another one which additionally uses that the row minima of the T matrix are non decreasing (simple+). All the methods were implemented in python and compiled with the numba compiler. We additionally include the time to sort the initially unsorted data of the same size for comparison. We generate our synthetic data set by sampling one million reals uniformly random between zero and one.
For low values of the minimum group size l the simple dynamic programs faster than the O(n) algorithms, with the simple+ algorithm outperforming the simple algorithm in terms of computation time. These simple algorithm become slower Uhan the more complex dynamic programs when the minimum group size & exceeds 250. When comparing the ((n) algorithms, the staggered algorithm is overall about 20 percent faster than other algorithms. Overall, we see that the algorithms including both the concavity of the cost function and the minimum maximun group size constraints, i.c., the simple+ and staggered algorithm, are faster than those algorithms that don't 't include both constraints.
14

---

Published in Transactions on Machine Learning Research (10/2024)
PCA
near-neigh random_10
random_
random_100
kmeans_0.5
kmeans_
kmeans.2 2_2
15000
10000
Reconstruction Error (SSE)
Reconstruction Error (SSE)
8000
10000
6000
5000
2000
10
20
30
40
minimum group size
minimum group size
(a) Dataset ELA
(b) Dataset Tarragona
Figure 6: Reconstruction Error for the Multivariate Microaggregation task on real world datasets. We show the Reconstruction Error or loss (lower is better) for the SSE cost function for different values of minimum group size k. We compare four different approaches, two projection based approaches 'PCA' and 'random' projection as well as two approaches designed for the multivariate case the 'kmeans' based approach and a nneiresttneighh based approach by [Domingo-Feve Ferrer et al., 2008). For the PCA and random approach, we use vector project the multivariate task into one dimension and solve the univariate microaggregation task with the methods introduced here. For the random projection approach one consist of making 10, 50, and 100 random projections (as indicated in the legend) and taking their minimum. For the k-means + cleanup based approach, we first performed k-means where the number of clusters k is dataset__ _eiittsssseeekee where f is a factor 0.5, or 2 as indicated in the legend. To make sure that the obtained data fulfills the minimum group size constraint we merge clusters of to small size with the closest clusters until all clusters are large enough. For the random, nearest-neighhor and k-means based approach we show means and standard deviation over 10 runs. On the ELA dataset (a), the k-means based approaches outperform the projection based approaches by large margin. The ncarest-ncighbor based approach is performing k-means based approach for low k but gets increasingly worse with increasing k. On the Tarragona dataset (b) the picture is not as clear. For low values of k s 5 the k-means based approach is better or equally good as the projection based approaches while for larger values of k the projection based approaches show less reconstruction error. The PCA based approach is usually slighlty worse than the random projection based approach. The nearest-neighhor approach on par with the k-means based approach for k less than 5 but it gets incrcasingly worse with incrcasing values of k.
par with the
In Figure 5 we compare the different ways of computing the cost functions exemplary for the simple+ and staggered algorithm. Within the same algorithm find that the method from section 4.3 is fastest with the default cumulative sum (eq. ? being close competitor. The numerically more stable method introduced in section 41 is about four times slower than the default method.
5.2 Solving Multivariate Microaggregation through projection
In practice one froquently met with Multivariate Micronggregation problems, i.c. there are multiple descriptors that need to be aggregated simultaneously. In this section compare approaches designed for the multivariate problem with approaches which work by projecting the multivariate problem into 1d, solving the univariate problem with the methods discussed here and then project the solution back to the multivariate setting.
The most simple approach to project the multivariate data into one dimension is to use principal components analysis (PCA). PCA identifies the axes of maximal variance. We then use the axis with maximal variance to project the multivariate data into a single dimension, we then solve the 1d problem obtain the chutter assignment. A similar projection based approach uses random projections, iee. sample random vectors
15

---

Published in Transactions on Machine Learning Research (10/2024)
with random values between zero and one as our projection vector. To achieve reasonable results, we try multiple random vectors and take the one with lowest multivariate loss. We compare these two projection based approaches with two approaches designed for the multivariate case. The first one works by obtaining a houristic solution to the k-means problem. Because there might be clusters which are to small, we merge the clusters of size less than k with the closest other cluster (measured by the distance of the centroids) until no cluster of too small size remains. We randomize the order of this merging procodure. As a sccond method designed for the multivariate case we consider the nearest- nearest- based approach by DDerrego-Ferrer et al. (2008). While the original proposed method allows for overlapping cluster:"] i.c. the subsets X, (compare Definition 1 need not be pairwise disjoint, we slightly modified their procedure such that they are pairwise disjoint for a more fair comparison. We found experimentally that whether we allow for overlapping clusters or not made pretly much no difference in the reconstruction erro (the mean reconstruction errors are within 6% of each other, none of the two clearly beating the other and the standard deviations are twice as large).
[
To evaluate these approaches we use two real world datasets that have been used in previous rescarch multivariate microaggregation (Domingo-Ferrer & Mateo-Sanz, 2002). The EIA dataset (Brand et al., 2002 consist of 4092 instances and 15 columns, of which we use the 10 numeric columns. The Tarragona dataset (Brand et al. | has 834 instances and 13 columns. We average the results of the k-mcans basod approach, the nearest-neighber based approach, and the random projection approach over 10 runs and show the mean and standard deviation. We measure the quality of the obtained clustering by the multivariate loss (SSE). The results are shown in Figure G
We find that on the EIA dataset the k-means based approaches greatly outperform, i.e. have lower recon- struction error, compared to the projection based approaches for almost all values of minimum group size k we considered. It is just that when & approaches 50 the two approaches become more similar in terms of their reconstruction error. The nearest neighbor based approach performs on par with the k-means based approach for values of k less than 10. For larger values of k it becomes increasingly worse compared to k-means based approach even overtaking the projection based approaches at k = 30. On the Tarragona dataset and low values of k >> 5 the k-means based approaches are winning by a small margin but for larger values of l the projection based approach are performin better than the k means based approaches. When comparing the PCA approach to the random prohjection approach, the random projection approach is usu- ally slightly better than the PCA based approach. From these preliminary experiments, it scems, that the projection based approaches might be a valid competitor on some datasets, while on other datasets, they are not viable. Overall the hearest-neighbe based method performs on par with the k-means based approach for small values of l (c.g. less than 10) and is inferior in reconstruction error for larger values of k.
6 Conclusions
We considered the problem of univariate microaggregation. We characterized properties of cost functions that lead to complexity improvements over the naive algorithm with exponential runtime. By mapping univariate microaggregation to a least weight subsequence problem we showed that UM for ordered mininizable cost functions is solvable in O(n²). If splitting is beneficial, a maximum group size constraint allows to improve this complexity to Okn). For ordered minimizable, concave cost functions a different strategy allows to find an optimal solution to univariate microaggregation in ((n) time and space on sorted data. These results apply to many popular cost functions such as sum of squares, sum absolute error, maximum difference as well as round up/down costs. By incorporating both a maximum group size constraint and the concavity of cost functions, we are able to provide an improved O(kn) algorithm (simple+) and an improved O(n)
"The definition of the algorithm is not sound unless this is assumed, even though this is not explicitly mentioned in the original source. In spirit of the presented algorithm we considered the below highlighted overlapping case.
'For the overlapping case but for each of them a set Y, C X, exists which highlights the non-auxillary nodes in X;- The Y; are pairwise disjoint and unify to Z. We obtain the reconstruction error the following way. For each element and compute the (squared) distance to the centroid of the correspond set X, To obtain the final reconstruction error we up those distances for all elements. This naturally captures a slightly different notion of k-privacy as the clements of the new datasct !2 are obtained by aggregating at least k clements of the original datasct. httpp::/gitthb... http://wwww..cacaaooooo/e//eeeaa http:///.hhaa....c..ara///ttttet
assume that there are not only the overlapping sets X; used to compute the cluster centroids
find the only set Y, it is contained in
16

---

Published in Transactions on Machine Learning Research (10/2024)
algorithm (staggered) which demonstrate faster empirical runtime in comparison to other algorithms in their respective complexity class.
Limitations In practice one is frequently met with multivariate microaggregation (MM) problems and one of the heuristics used to solve MM problems is to devise an order on the points (see (Mortazavi 2020) and references therein). The resulting ordered multivariate micronggregation problem sometimes referred to as a univariate microaggregation problem even though it really is a least-weight subsequence problem with multt-dimeenional cost functions. These multi-dimensional cost functions may longer be concave the concavity of the cost functions relies on the sorted (i.e. arranged in increasing/ /ecreasing order rather than any fixed but arbitrary order) 1D nature of the points. Thus the presented ((n) algorithms are not applicable to such ordered multivariate microaggregation problems. As the simple (km) algorithm does not rely on the concavity of cost functions, it can still be used to solve the ordered multivariate microaggregation problem a multi dimensional equivalent of the splitting is beneficial property holds.
It is well known, that the privacy concept of k-anonymily may provide insulficient protection if for example the confidential attributes are not sufficiently diverse. Caution should thus be taken if k-anonymity, microaggregation to achieve k-anonymity, is applied in practice. For practical anonymity guarantees, the
concept of differeniaal privacy (Dwork et al. 2006 Dwork 2008 provides a more robust protection.
While k-anonymity relies on the intuition "hidden in a crowd of size at least k", the key idea of differential privacy is "plausible deniability", L.e. whether or not any individual is included in the data cannot be said with certainty. To achieve differential privacy guarantees, usually the output of an algorithm is sufficiently perturbed. Li et al. (2012) showed that using k-anonymity, it is possible to essentially perform input perturbation and still achieve differential privacy if the k-anonymity type algorithm is augmented with two steps. First, the k-anonymity algorithm needs to be e-safe: Intuitively this means the k-anonymity algorithm needs to output non-optimal clusterings with nonzero probabilities. Second, k-anonymity is applied to a subsample from the original dataset instead of the full dataset (for the full details see (Li et al. 2012)). )
Concave costs where splilling is nol beneficial The majority of cost. functions considered are concave and have the splitting is beneficial property which allows all the presented algorithms to be applied. Yet, there are concave cost functions which do not have the splitting is beneficial property. As a simple example consider adding a constant group cost 5 to concave cost function C which also has the splitting is beneficial property to penalize having too many clusters (i.e., we obtain the adjusted cost function ((i, = C(i,)) + 6). This adjusted cost function is still concave but no longer has the splitting is beneficial property. Thus the generic O(n) algorithms (Wilber 1988 Galil & Park 1990) may still be used to solve UM problems for the modified cost. function C while the O(kn) algorithms (simple, simple+) and the staggered algorithm are not applicable.
Relation to k-means The definitions presented here also allow to have more fine grained understanding of other 1D clustering problem with different cost functions. As example let us consider the k-means problem which restricts the number of clusters to be exactly k. An existing Okkz² algorithm [Gronlund] ct al., 2018) solves the 1D k-mcans problem if the cost function considered is ordered minimizable. If the cost is additionally also concave, O(kn) and Onn log U algorithms exist (Gronlund et al., 2018).. The splitting is beneficial property, while not explicitly used in algorithms, seems to be implicitly used when formulating the k-means problem. The most popular formulation of the k-means problem asks to minimize the clustering cost subject to exactly k clusters, while minimizing costs subject to most k clusters could also be thinkable. However, these two formulations will result. in idantical optimal clusterings if the cost function has the splitting is beneficial property.
Mixed UM and k-means scenario Another way to avoid using overly many clusters in UM setting could be to impose a maximum number of clusters constraint in addition to the usual minimal group size raint. This would correspond to a mixed UM and k-means scenario. We implicitly showed that the considered cost functions are ordered minimizable even in a mixed UM and k-means scenario, as cost functions that are g-partition ordered minimizable also encompass this mixed scenario. Hence, algorithms used solve the 1D k-means problem (see (Gronlund et al.] 2018) for many such algorithms) work correctly in the mixed UM and k-means scenario if we adapt the cost function as explained in eq. (3).
Olog U. is number of bits used
17

---

Published in Transactions on Machine Learning Research (10/2024)
Regularized UM problem The usual UM problem forbids any clustering with too few entries, which might be overly restrictive when k is larger. In such cases it might be worth considering regularized UM problem, i.e., we don't 't entirely forbid invalid clusterings but instead return an additional cost when the minimal cluster size constraint is violated. This can for example be achieved by defining the regularized cluster cost as
C(i. + Ak--(j- - (i-i)) j k
0
else
with regularization parameter À 2 O. By adjusting the regularization parameter to large we can make it more and more unlikely that the cluster size constraint is violated. If was concave, the regularized UM problem may also be minimized by the generic concave algorithms (Wilber 1988 Galil & Park 1990). Similarly, if splitting was beneficial for C, the regularized UM may be solved by slightly adjusted standard algorithm in Okk)).
References
Alok Aggarwal, Maria M Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of matrix-scarching algorithm. Algorithmica, 2(1-4):195-200 208, 1987.
Charu C. Aggarwal and Philip S. Yu. A General Survey of Prinacy-Preservinn Data Mining Models and Algorithms, pp. 11 52. Springer US, Boston, MA, 2008.
Ruth Brand, J. Domingo-Ferres and J. M. Mateo-Sanz. Reference data sets to test and compare SDC methods for protection of numerical microdata. European Project IST-2000-2500 CASC, 2002. URL .dff
https: / http///eeeeeeeheeeeeeeee cbs nl1
Rainer E Burkard, Bettina Klinz, and Rüdiger Rudolf. Perspectives of monge properties in optimization.
Discrete Applied Mathematics, 70(2):95 161, 1996.
Jordi Casas-Roma, Jordi Herrera-Joancomarti, and Vicenç Torra. k-degree anonymity and edge selection: improving data utility in large networks. Knowledge and Information Systems, 50:447-474, 2017.
D Delays and MN Anwar. Masking microdata using micro-aggregatiin. Journal of Official Stalistics, 14(4): 449, 1998.
Josep Domingo-Feri Ferrer and Josep Maria Mateo-Sanz. Practical data-oriented microaggregation for statistical disclosure control. IEEE Transactions on Knowledge and data Engineering, 14(1):189-20) 2002.
Josep Domingo-Ferrer and Vicenç Torra. Ordinal, continnous and hetcrogencous k-anonymity through mi- croaggregation. Dala Mining and Knowledge Discovery, 11:195 212, 2005.
Josep Domingo-Ferrer, Francese Sebé, and Agusti Solanas. A polynomial-time approximation to optimal multivariate microaggregation. Computers Mathematics with Applications, 55(4):714-73) 732, 2008.
Cynthia Dwork. Differential privacy: survey of results. In Manindra Agrawal, Dingzhu Du, Zhenhua Duan, and Angsheng Li (eds.), Theory and Applications of Models of Computation, pp. 1-19. Springer, 2008. ISBN 978-3-540-79228-44 doi:
1.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, pp. 265 284. Springer, 2006. ISBN 978-3-540-32732-5. doi: 11100/11681878 14.
Z Galil and K Park. A lincar-time algorithm for concave one-dimensional dynamic programming. Information Processing Lellers, (3)6)330 311, 1990.
II the regularized UM scenario, need also consider clustcrings in which clusters contain less than k points. This corresponds the red entries in Figure 3 of which there are only k-1 per column. We thus process 2k-1 entries per column resulting in overall O(kn) runtime.
18

---

Published in Transactions on Machine Learning Research (10/2024)
Allan Grenlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, and Mingzhou Song. Fast exact k-means, k-medians and bregman divergence clustering in 1d, 2018.
Stephen Lee Hansen and Sumitra Mukherjee. A polynomial algorithm for optimal univariate microaggrega- tion. IEEE transactions Knowledge and Dala Engineering, 15(4):1043-1444 1044444-44,, 2003.
Md Enamul Kabir and Hua Wang. Microdata protection method through microaggregation: A median-based approach. Information Security Journal: A Global Perspective, 20(1):1 8, 2011.
Ninghui Li, Tiancheng Ti, and Suresh Venkatasabramanian. t-closeness: Privacy beyond k-anonymity and I-iieesity. In 2007 IEEE 23rd International Conference on Data Engineering, pp. 106 115, Istanbul, Turkey, 2007. IEEE.
Ninghui Li, Wahbeh Qardaji, and Dong Su. On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In Proceedinggs of the 7th ACM Symposium on Information, Computer and Communications Security, ASIACCS '12, 32 33. Association for Computing Machinery, 2012. doi:
Ashwin Machanavajjhala, Daniel Kifer, Johannes Gehrke, and Muthuramakrishnan Venkitasubramanian. I-diversity: Privacy beyond k-anonymity, ACM Trunsactions on Knowledge Discovery from Dala (TKDD), 1(1):3-es, 2007.
Reza Mortazavi. Improved univariate microaggregation for integer values. ISeCure, 12(1):35-44 43, 2020.
Anna Oganian and Josep Domingo-Ferrer. On the complexity of optimal microaggregation for statistical disclosure control. Statistical Journal of the United Nations Economic Commission for Europe, 18(4): 345 353, 2001.
Lue Rocher, Julien M Hendrickx, and Yves-Alexandre De Montjoye. Estimating the success of re- identifications in incomplete datasets using generative models. Nature communications, 10(1):1 9, 2019.
P. Samarati and L. Sweency. Protecting privacy when disclosing information: k-anonymity and its forcement through generalization and suppression. Technical report, Computer Science Laboratory, SRI International, 1998. URL http::/www.co. csl. sri www.:/pppppessrrirr--------
Pierangela Samarati. Protecting respondents identities in microdata release. IEEE transactions on Knowledge and Data Engineering, 1316):1010-1027, 2001.
Latanya Sweeney. k-anonymity: A model for protecting privacy. International journal of uncerlainly, fuzziness and knowledge- systems, 10(05):557 570, 2002.
Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418- 425, 1988.
Xiaolin Wu. Optimal quantization by matrix searching. Journal of algorithms, 12(4):663 673, 1991.
Yan Yan, Anselme Herman Eyeleko, Adnan Mahmood, Jing Li, Zhuoyue Dong, and Fei Xu. Privacy pre- serving dynamic data release against synonymous linkage based on microaggregation. Scientific Reports, 12(1):2352, 2022.
19

---

Published in Transactions on Machine Learning Research (10/2024)
A Additional algorithms
A.1 Pseudo code for the classic algorithms (simple/ simple++
Input: sorted array v, minimum size k, cost function calculator C
Output: array implictly representing the optimal univariate micronggrogation of let -length(e)
if < 2k -1 then
return all zeros array of length
C.do preproccssing(v, k)
MinCost/Argmin = zero based arrays of size n++1
MinCost(00 =
for j (I,...,n) do
Argmin|j] arg minosicy MinCost(i] + C.calc(i, j)
MinCostti] = MinCost[Argnnn [Argmini|] + (.rgal(Argginnj)).. j)
10 return Argmin [1n]
Algorithm 2: Pscudo code for the classical algorithm used to solve least weight subsequence problems. If this algorithm used to solve univariate microaggregation with ordered minimizable cost functions, the constraint the arg min in line 8 becomes 0 S < k. If splitting beneficial the constraint the arg min in line 8 is max(0. - 2k + 2) sisj k (this is the simple algorithm). Lastly, for concave cost functions that also have the splitting is beneficial property, the bound on the arg min is max (Argmin(j-]], 2-2k+2) < i N - k with Argmin(0]=00 (this is the simple+ algorithm).
A.2 Pseudo code for the backtrack algorithm
Input: zero indexing based implicit cluster array Output: array explictly representing the clustering
out zero indexing based array of same length as p-length(b); 0
while (rue do NumClusters +=1
for i E {blp p-
p- 1} do L out = Num Clusters
6
b-plpp
if p = 0 then break
10 for i e (O...., (eng(h)))) - 1} do
11
out[i] Clusterss out(i]
12 return out
Algorithm The backtrack algorithm converts an implicit cluster representation array into an explicit cluster representation. All the presented algorithms return such an implicit representation. For example implicit cluster array 1, 2] represents the clustering [0, 1, 2, 2, that is the first and second element their own cluster, and the remaining elements are in one cluster. The backtrack algorithm runs in (n))
20

---

Published in Transactions on Machine Learning Research (10/2024)
B Mathematical details and proofs
B.1 Multivariate microaggregation is NP-hard for many cost functions
It was previously known that multivariate microaggregation is NP-hard for the sum of squares error cost function. We noticed that the proof provided by Oganian & Domingo- Ferrer (2001) could be easily adapted for other cost functions as well.
Let 4(C), {3, 4,5) denote the minimal cluster cost for cost function C computed for the structures of size outlined in (Oganian & Domingo-Ferrer 2001]. For (multti)set X = [11,-- ...p with æ; R let denote with X 1z11 , Lp e, the multi-set of values projected onto the i-th standard basis vector.
Theorem 12 (Gencralizing the result from Oganian & Domingo-Forrer 2001
Microaggregation for
cost. functions ((d) Ei= (() is NP-hard in dimensions d 2 2 and k = 3 if splittting is beneficial
for cost function C, and the ratios of minimal structure cost are ((()) > [CC)
3 and (())
Computing the E (3, 4,53 values for the cost functions corollary 7 we get the following:
Corollary 13. Microoggregation NP-hard in dimensions and for the cost functions SSE, SAE, and Round up/Rone m/Round down cost.
The original result by Oganian & Beasingo-Ferrer (2001) dealt with SSE only but the proof allows easy adaption for SAF, and round up/round down cost. Unfortunately, theorem 12 is not applicable to the maximum distance cost as both I; ratios are too small.
B.2
Total monotonicity and concave cost functions
B.2.1 Monge matrices and their transpose are totally monotone
Before we start with the proof for concavity we recap the relationship of concave cost functions and totally monotone matrices. For concave cost function we start by rearranging the quandrangle inequality eq. (1)
C(a, c) C(a, d) d(b, 0
We then notice that now C(b,e) c) - C(bb d) < 0 + C(a, C(a, d) < 0. we now consider the matrix with entries C₁ C(i.j), all 2 by 2 submatrix of have the form
((a,,) C(a, C(b.c) C(b,d)
for suitable choice of of the integers a < b, < d. To check for monotonicity we see that c(b,c) < C(b,d) which is equivalent to Cbb.c) - Cbb, d) < which by our previous equality implies C(a,c) - C(a, d) < 0 e
C(a, c) < da, That means that any by 2 submatrix totally monotone. Thus the entire matrix is totally monotone.
For the transpose C we find that 2 by submatrices are of the form
(C(a,c) C(b,c)) (Cla.a) d)
To check for total monotonicity need to show that C(a, d) C(b,d) C(a,d) C(b, d) < 0 implics C(a,e) < C(b, + C(a,c) c(b,c) < O. By rearranging the quadrangle inequality we find
Cla, - ((b,c)-(((b)) C(a, d) - C(b, d) for 0 < a < <b<cedsn
Now C(a, -ic,dd)C((bd)) < 0 C((,c)-C((bc) which is exactly what we need such that any 2 by 2 submatrix of CT is totally monotone. Thus the entire matrix C is totally monotone.
21

---

Published in Transactions on Machine Learning Research (10/2024)
B.2.2 Proof that M is totally monotone
We prove total monotonicity of M by showing that all 2 by 2 submatrices fullfill the necessary equations. We never explicitly consider a submatrix but we choose two entries in the same row but different columns (coll < col2). We then compare the values of M those locations (vail:= M coll val2:= M col.) Depending the size of the values, this imposes requirements val2) or the entries above (in case of vall I val2). If row' is such a row either above or below, we refer to the entries in the same columns as before as vall' := Mow val2":= M.w' cowl
either the values below (in case of vall
MT of the adapted cost in eq. (5) Instead of referring to explicit values, we refer to the values by their colors. If the cluster corresponding to the entry is too small, the color is red else the color is green (these are the two cases in eq- (5))
Case vall=green, val2- = green: vall I val2: The pairs above are either green-green, green-red, or red-red. For green-green pairs monotonicity is guaranteed by eq. (1). This implies total monotonicity as the transpose of monge matrices are also monge Burkard et al. (1996), monge matrices are totally monotone Burkard et al. (1996) and you add constant values to the columns of totally monotone matrices they remain totally monotone Burkard et al. (1996). For green-red, and red-red pairs by design vall' val2'. Overall values above coll less than equal to those in col2. vall > val2: The only case if green which is correct by monotonitcity.
Case vall= vall=green, val2=red: The only case is vall val2, the pairs above are either green-red red-red in either cases the values above coll smaller than those above col2.
Case voll=red, val2-red: The only case here vall val2: all entries above are red-red as well for which vall' val2"
M of the adapted cost in eq. 66 As before, instead of referring to explicit entries, we refer to the entries by their colors as visible in Figure 3 iee. the first case in eq. (6) is red, the second orange and the third is green.
Case vall=green, val8- green: vall s val2: The cases above are the same as in the previous consideration.
vall > val2: The pairs below are either green-green, trange-green or orange-orange. For green-green pairs monotonicity is guaranteed as in the vall < val2 case. For orange-green and orange-orange pairs, vall' > val2' by design.
Case wall=red, val2-red: the only case here is vall < val2: all entries above are red-red as well for which vall' < val2*
Case vall =oln=erange, val2-green The only case is vall > val2, the possible pairings below are orange- orange or orango-green. We see that the values below coll are larger than those below col2.
Case wall=orange, val2-red: The only case is vall < val2, the pairs above are either orange-red or green-red. In both cases the values above column 1 are smaller than those above column 2.
Case voll=green val2=red: The only case is vall < val2, the pairs above are either green-red red-red in either cases the values above coll are smaller than those above col2.
Case vall=orange, vol2=orange: The only case is vall val2, the pairs below are orange-orange. Thus the values below column 1 are larger than those in column 2.
B.3 Computational complexity of computing cost functions
This section shows, that all the cost functions presented in corollary 7 can be computed O(1) performing at most Onn) time for preprocessing and using at most O(n) space. Throughout this section we assume that the input data sorted, ie. i = x, S Zz. We also assume that such that X1,; (1441.... is well defined.
22

---

Published in Transactions on Machine Learning Research (10/2024)
B.3.1 Sum of absolute errors
During preprocessing we compute and store the cummulative sum s(1) = =ii= 21- The computation of that cummulative sum is O(n).
For (mullii-)set denote with (A)) the we note, that
LAi
smallest/largges elements of A. Let 1 | then
SAE(1,))
E
Σ
xE(X.5)2 xE(X,,))
=(() s(j 1) (s(2 + si))
which is O(1) if the s() are stored in an array.
B.3.2 Maximum distance cost
For the maximum distance cost Coo have
Coo (i,5) = max
1x
3i+ + +0j
F4+1
zEXi,
2
2
which is O(1) if the z; are stored in an array.
B.3.3 Round down/ round up cost
Similar as for SAE for precomputation compute the cummulative sum s(i) Ei= 21, s(0) in ( and store all of the s(i) values. Then the round down cost is
Ci(i,))
Σ x -1-2 = s(i) s(() -i) 1i+11
The round up cost is
C+i,5) = Σ
21 = ( (1-1)z f)z (s(s) s(i))
1=#+1
Both are 0(1) if the x; and s(i) are stored in an array.
B.4 Concavity of cost functions
B.4.1 Maximum distance cost is concave
In 1D the maximum distance cost defined as Co (a, = max |a] - Fa.bl where Fa.. = 2s+ma+1 is chosen such that minimiies the max expression. Thus in ID, the maximum distance cost. can be written as Coo (a,b) = Jay Pa..ol = |Ia+1- Fa..bl = Ts Fs-Fot1
2
We can now show, that the maximum distance cost Zo 20-1b=1 Coo (a, d) Coo (b.
is concave: (a. c) (b. 20-2at1
24 -
23

---

Published in Transactions on Machine Learning Research (10/2024)
B.4.2 Round up/round down costs concave
In 1D the round up cost is C+(a, = Emaat lob zıl = (b-a)xb -Ei-ati Dt. We can now show, that the round up cost is concave:
C((a + Cb),
<> (c- - 0) + - b))
Ti
im++1
i=b+1
d
S (d - aa=aa)za(( (c- -b)xe-
Σ
24
==++1
imbbl
(c- a)xx + (d- b)og 5 (d-a)ri + (c b)ere
+ 2 bid -aTT bac
+ (b- a) Th S (b- aaaa
+ Io S Id
which is true as the points are ordered increasing order. We can do similar argument for the round down cost. (a, = Eimat l0, 102-x,0 xal Eima+1 Iz (b a) aa.
( )
d
+
Fi 8i- (c a)tl - (d - b))b+11
i=0+1
t=b+1
c
S
Σ F4- Σ
3; (d a)xat1 - (c- b)rb+1
im0+l
i=b+1
+ (cc- - a) d)Tat11 (d b) $ (d - a) a0+1 - (c- b)zb+1
3 Co + d3 5 -d CDb+1
+ (d c) c) S (d - c).b+1
+ Ia+1 S Tb+1
which is true as the points are sorted in increasing order.
B.4.3 SAE cost is concave
2 /lallest/largest elements. For brevity let us define s(A) = EvEA x. Let A, B, C be the three sets obtained by the cut indicies a, b, c, d (A (ratt....,,. D.
For a (set A let us denote with (A)1/2 the
[A|
B (1b+1, Re C (fett...., Then quadrangle incquality for SAE reads:
(( (((,c) C)(a,c) ((a,d)
$ +s((AABB))+ (UAAAUU))-++((NND))---00C0000000
S <=((ANVFUU))))(((((RR)))))))(())
24

---

Published in Transactions on Machine Learning Research (10/2024)
To simplify the above expression observe the following relations:
(AUB), _ (AUBUC),
RABC-AB,I = (AUBU)))(AUB))
(BUC)2 _ (AU BUC)2
RABC-BC22 (AUBU C)2 (BUC)
(B), (BUC),
RBC-BA1 B,1 = (BUC), (B)
(B)2 _ (AUB),
RAB-B22 = (AUB) (B)2
Then we have
C((a,)) + C((b,)) C((ad)) +
+ s (BAABCAAB.) + &RAB--B (RABBC-BO.)) + RBC-BB) B,1)
which is true as s(RAnC-AR)) S SBRBC- B.I) and s(RAB-BA S 8 (C:) One can see that the first expression is true by increasing the size of A gradually. If [A| = 0 then certainly the Ihs and rhs are the same. If we now add elements to A which are no larger than those in B then the lhs expression will only get smaller. One can employ a similar trick for the second expression by adding elements to C' which no smaller than those in B, which only increase the rhs expression.
B.4.4 SSE cost is concave We already explained how to compute the SSE cost in O(1) using O(n) for preprocessing in section 4
B.5 Ordered minimizable
B.5.1 Proof of Theorem
Before we start with the actual proof lets provide some clarifications regarding multi-sets. When calling for the I < [X] smallest elements of multi-set X, mean the multi-set S C X of size which fullfills (x) S x.
We conduct the proof of theorem 6 two steps. First we show that q-partition ordered minimizable for all q implies ordered minimizable. We then show that if a cost is 2 partition ordered minimizable it is 2 2-partition ordered minimizable for all q-
Lemma 14. If cost function is q-partition ordered minimizable. for all q then it is ordered minimizable.
We prove lemma 14 by contradiction. Lets assume that it is not enough to consider only pairwise ordered partitions when finding any partition minimizing a total cost which is q-partition ordered minimizabe for all q. But then there is a partition P (wlog. PP| = q) which minimizes the lotal cost. TC subject to the either the UM or k-means constraint. But then as the total cost TO is q-partition ordered minimizable we are guarantced a pairwisc ordered partition p' with has the same multisct of sizes as but no larger total cost. Thus P' also respects the UM k-means constraint. Thus it would be enough have considered only pairwise ordered partitions when minimizing the total cost on the relevant, partitions, which concludes contradiction.
Proof. Now we show that if cost is 2-partition ordered minimizable, then it is q-partition ordered mini- mizable for all q by induction on g.
The base case the assumption. Assume the TC is q-ordered minimizable. Let P = i X,+1 a (qrtt-partition. We can construct a pairwise ordered partition P' which has no worse TC than P: Let A = X1. From 2-partition ordered minimizable we know that we can obtain sets B C++1 pairwise order(A;, X++1) (see corollary 7 We then define Ait1 min( B1, C.t) and X, == max (B,1,, C.+)). Note that A411 contains the smallest elements in U X,. We can then define the partition
P = (8i, (X....., 8 Ai, X ..... 8.
25

---

Published in Transactions on Machine Learning Research (10/2024)
We that P1 P and x The latter is consequence from
9+1
TC(P++) = Σ +(x))+ + c(Arn) +
Σ c(x,)
5=1
j=tt2
i-1
9+1
<T((P:) = Σ C(X))++((M))))) +(A)+
+
Σ C(X;)
j=1
/=4+
which is equivalent to
C(X,) + C(A+1) S C(A.) +((++1).
Here we note, that either |A41l = [x++1 and [X, = |Ail or |4+1 = |Ae and [X,] = (X4+1]. In either case the equations can be written as
TCHL RJ) S STC(Y,
(9)
with [r|| [ R imizable which have by assumption. Overall have found partition P I( Xg. Ag+1 H with TC no worse than the TC P. Now we consider the minimization problem of TC on 12,A, subject to partitions of size q- By the induction hypothesís are guaranteed a pairwise ordered partition ( &g &,, Ag+1
| and I., R being pairwise ordered but this is exactly being 2- 2-partition ordered min-
that minimizes TC on Ω Ap+1- Now we have found (q+1) ordered partition p = which has the same size multiset and no worse TO than but is totally ordered (remember the X; are pairwise ordered and all elements in Ag+1 are no larger than any elements in any of the Xt). This concludes the induction.
B.5.2 Ordered minimizable and quadrangle inequality
In this subsection provide evidence that quadrangle inequality and ordered minimizable are indeed not the same concepts by providing a simple counter example. Lemma 15. Quadrangle inequalily does not imply ordered minimizable.
Proof. Let our universe Ω I2 be finite and
Cmiu (X) == min(X)
Then by the following Cuin fullfills the quadrangle inequality (a < b < d)
Cmin (a, c) + Cuin (b, d) S Caunn (a, d) Cuin (b,
Ja+1 + xb41 S Ja+1 + Tb41
The last line is certainly true.
We will now show, that Cuuin not ordered minimizable. Let |9]] 2 and let wi < W2 < w/ be the smallest, second smallest, and third smallest element of the universe Q. Let the multi-set ::= Ω (w1, wa.. Then for A {wi, wg) and B {w2) U R be two sets then TC(AA, B}) W1 + We but in every ordered partition with mi, [R]) 2 2 we have that wa and We are in the same set. But this means for any pairwise ordered sets L and R with min [R)) 2 2 we have TC R}) 2 wi tw > TC{AA, B)). Thus Cuin is not ordered minimizable.
B.5.3 SSE 2-partition ordered minimizable
Looking the variance var(X) 1 ExEx(1 8)2 1 simplification. We now note, that SSE(X) var(X) x?) x2X2 thus when comparing two partitions
1XT (Erex x²) X2 where the latter is common
26

---

Published in Transactions on Machine Learning Research (10/2024)
Pi and P2 of the same original set we sec, that
TSSE((2) (S))((P)
Σ Xx 2xx
-
Σ x XEP=
XEP
For the case of two partitions P1 = (A+ A, BD and P2 = {(A DBBB B+ AB with A|= [B] but À # B (think of exchanging elements from + Ā with the B elements in B + B). This means
TS) - 3S)
A AA 11 B+ B+B S A B A+B BB+
+ R A+A DAABH 14 2 AB+ B+ - BB+ B
Where ns denotes the size set and μs denotes the average of the set p. To treat the Ihs and rhs simultancously, lets consider multisets X, Y with |Y| |2|:
"x+81 X+Y - 7x21" X+2
1
(xx + sy 28x8y 83 - 2z 28x82)
"x+8
1
(st 28 - -28x82)
nx+8
1
(sy 8z) (er 8% + 28x)
"x+8
(sy - sz) (ux+Y ux+2)
Bringing this logether with the previous equations yields
TSSE(P1) S TSSE(P))
+ (5 - 8B)(M + MA+B) 2 ($ 88)(H + KB48)
+ A + P S M π + HB+
MA+B PB+ $ 1B+B PA+A
Where the the second last line is true s < $p. If we can maximize the right hand side of the last expression which is only function of the partition Pı, this is the same minimizing the TSSE of Pi with respect to P2. The maximum of the rhs is achieved by choosing that B and contain the largest elements while A and contain the smallest elements. This naturally fullfills $ < 8 as |Å] = |B] (remember A B). Thus we conclude that for all 2-partitions P2 we can find pairwise orderd P1 which has no worse TSSE, ie. TSSE is 2-partition ordered minimizable.
B.5.4 Infinity norm is 2- 2-partition ordered minimizable
We denote the saaalesstlarrges element in Ω with l/r. Lets assume we are given a partition P the elements in Q into and B. Wlog lets assume E A. We choose two sets and R such that L contains the |A] smallest elements and R the remaining elements, then
Coo Cxo S Coo + Coo (B)
m.
-1 r min R))
max(A) - max B) min
2 +
max (A) min(B) if max max(B) r max B) min(B) B) if max(A) =r
+ max (T) min( R)
In the first case, we have that max(L) S max(A) as contains the smallest elements and |A| = [L]. Further, min(B) < min(R) as R contains the largest elements and |B] = [R]. In the second case we observe that the left hand side is always non positive while the right hand side is always non negative.
27

---

Published in Transactions on Machine Learning Research (10/2024)
B.5.5 SAE is 2-partition ordered minimizable
For multiset A we denote with 01/0s the multisets of size
|A|
containing the smallest /largest elements
of A. We define b, 44, similar for multisets B, L, We then note, that SAB(A) = = - + Emang a irrespective of whether |A] is even or odd. Lets consider a partition of the elements in Ω into two sets A, B. Let us further the multisets 61/2 == 4//2 U 11/2 and d1/2 == 41/2 U 11/2- In a slight abuse of notation let us denote the index (i.c. position in an order of Q2) of the i-th smallest clement in C1/2 as C1/2(1). Then #e1/2(1) is the smallest, #2)/2(2) is the second smallest element of 01/2 and so on. We similarly do that with the sets d1/2 (i.e. =d),2(()) the i-th smallest element of d1/2). We define L/R as the sets containing the amallest//lareest elements of Ω. The size of L is min([A]. |B) if d2(1) I max([a1], (b1l) and max([A], [B)) otherwise. The size of R is [9]] - |A].
Lets us first consider the first |41 of the sets 21/2 and d1/2. For S 141 certainly (1 (i) (these are the 1 smallest elements of 22). Further, (1) S (1) as (1 & d2(1) and the C2 continuc consocutively for the next [4]] - elements. In the case |L| min([A], [B) the relation c2(1) I d2(1) is pretty obvious as in this case (2) minimal among all partitions with the same size. the other case, we use that now d2(1) > max(|ai) [6 + c2)).
For the remaining rral elements in 2 d1/2, let i $ |ral and we can do a similar argument but from the other direction. For ease of notation we set b4 = [1 |ril We observe that cz(ng -t) = d2(ng -i) as these are the Inil largest elements. Also ci - i) 2 di (mg -) as ci (ng) 2 (ng) and the next |ril smaller elements are consecutively. In the case [4| = max([AI,|BI) the relation c1(2g) 2 di (n(n)) is pretty obvious as in this case (14) is maximal among all partitions with the same size. For the other case let |A| s [B]. We use that now d2(1) < max([ar), (611) + 1 which implies that max(a;) I d2((1)
max((a1), [6 l) or in other words all indices of elements in di that are larger than max([a1), | (bil) are from b₁. Because there are at least b elements larger than those in d1, we can conclude that d1 (n S n |b S es (nz))
Turning back to the SAE we find that
SAE(L) + SAE(R) S SAB(A)+ + SAE(B)
la ||b1 Tell)) -o((() S
|a l
Σ
Jdl()) Id.(()
1=1
Looking at individual terms we find that (T) - Ee, S. (d) dd If the individual Ihs terms are no larger than the rhs term, then certainly the Ihs sum is no larger than the rhs sum.
(1) because c2(1) S d2(1) and (i) 2 (i).
B.5.6 Round up/down costs are 2-partition ordered minimizable
Let (A, B) be a 2-partition of Ω. Wlog max(A) < max(B) then certainly (B = max(Ω).. We now choose L, R to be the anallest/largess elements of Ω with sizes |A] and [B] respectively. Then the round-up cost is
+ +G S (+A)+++C C,
# E.Er max(L))++) E.en EE max R)) - REA max(A) >.en Max(B)-
+ |A max(m) < |A max(A)
Where a lot. of terms cancel as each & appears exactly once, and max B = max R. Certainly max(L) S max(A) as both have the same number of elements and max L is minimal over all sets of that size.
We can do similar argument for the round down cost. Let {A, B} be a 2-partition of Ω. Wlog min(A) S min(B) then certainly min(A) min(A). We now choose L., R to be the smallest/ waallesttlaaggeee /largest elements of Ω with
28

---

Published in Transactions on Machine Learning Research (10/2024)
sizes |A| and [B] respectively. Then the round-down cost is
EeEL m-min(L)+ E. (-min(R)s) (R)s min( Exes min(B)-a
+ BB min (R) B| min
min R min(
Which is true min(R) is maximal among all sets of its size.
B.6 Negative results on ordered minimizable
The mean absolute error (MAF(XX= = x Exex | Mcdian(X)) is not ordered minimizable. One counter example is: For Ω (1,,0,0,00,0 1B. the partition (1 11-1, 0, {(,, 0B} has cost 1 but the two pairwise ordered partitions { (1,1,,0,,01 {0, 1}} and ({-1,0), 80, 0, 1B} both have costs 4
The & cost (X) = (XSE(X)) not ordered minimizable. One counter example For Ω 0, the partition [f-1,1.0}, [O.0 has cost v2 = 1.41 but the two pairwise ordered par-
titions {|l 1, 0}, {0, 13} and [[]-1,0; (0,00)00000))) 13} both have costs v + 3 1
The mean round down error (d-(X) = 지 Evex x mmi((X) is not ordered minimizable. One counter example is: For Ω f0, 0, 0, 1,2, the partition {1(0, 0, 2B, [1.1]}} has cost 1 but the two pairwise ordered partitions 0, B. [1,2)) and (O, f0, 1, 1,,) have costs and respectively.
One can construct similar counter example for mean round up cost. The mean round up error (X)() I
[X] Exex max(X) x) not ordered ménimizable. One counter example is: For f {00, 1, 2, 2}, the partition {1002 2, 2B, (1,11)) has cost 1 but the two pairwise ordered partitions 1, (2,2}} and {0, 1.. 2, have costs 1 and respectively.
B.7 Ordered minimizable but splitting is not beneficial
We were wondering whether could provide cost function which is ordered minimizable but does not have the property, that splitting is beneficial. Let us denote with X X>л{(x) the set of elements in the set X larger than median of X. Let our universe consist only of non negative reals i.e. Ω R2. Then we can define the a cost function
C (x()
2
Σ x
X 2EX>
If you consider your universe to be a set of item prices, the cost function describes a scenario where you pay discounted price on only the most expensive half of items. The discount parameter S a S controls the indicate that you get significant discount if you buy
amount of discount provided. Values of a close in bulk, while low values of indicate very low discount when buying bulk.
The cost function C* (X) is ordered minimizable but it does not have the splitting is beneficial property for a > O. For a = an optimal UM clustering is just single cluster containing all points independent of the actual universe Ω.
29


Reviews:
[{"review_id": "bVKyzo5FHG", "reviewer": "Reviewer_JNUo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In what follows, the strengths of the paper are listed:\n\n* The univariate microaggregation problem formulation as an instance of the least weight subsequence problem is interesting.\n* Inspecting the property of \"splitting is beneficial\" is interesting, and showing various functions that adhere to such property is indeed eye-opening.\n* Utilizing the concavity of certain loss functions led to faster time is also a novel approach.\n\nWhile the ideas in the paper are combined meticulously, there are some weaknesses with the approaches:\n* Some of the writing needs to be addressed (see next section)\n* The algorithms seem to work explicitly for the univariate microaggregation problem, while not working directly with the multivariate microaggregation problem due to the sorting-related phase, as well as, losing the concavity property which allows for $O(n)$ time. The authors have mentioned this issue.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes algorithmic solutions to the univariate microaggregation problem. The authors first reformulated the problem to an instance of the least weight subsequence problem which requires $O(n^2)$ time to solve. The authors then discussed certain properties associated with the cost function which can lower the timing to $O(kn)$ time, and with more properties, one can achieve $O(n)$. Theoretical guarantees are given, along with some experiments highlighting the speed associated with the provided algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Writing related issues:\n  * Change \"proof\" to \"prove\" at the third line below equation 6.\n  * Add citation to the second line below equation 1.\n  * You meant to say lines 15-17 instead of Line 16 at the caption of Figure 3?\n  * Right the start of section B.2.2, you meant to say $\\tilde{\\mathbf{M}}_{row,col2}$ for $val2$?\n\n* Experiment-wise:\n   * I understand that it is problematic to apply your approach to the multivariate microaggregation problem, however, I still suggest the authors to run their approach on at least two real-world datasets.\n\n* Questions:\n   * In the setting of the problem, to ensure some sort of privacy, the microaggregation problem is given to address this problem. Why did the authors not consider using matrix sketches? for example for the $k$-means problem which in turn gives a smaller set of points that might not even be a subset of the data such that solving the optimal $k$-means on that data would give an approximate solution to the optimal solution obtained when running the same algorithm on the entire data?\n   * Is there no way to apply your algorithms to the multivariate microaggregation problem using the projection technique? I understand that this would be considered to be a heuristic more than a provable approach. In case one can, how would you measure the credibility of your approach? I.e., what would be the metric for the effectiveness of your approach aside from running time?", "broader_impact_concerns": "I have no concerns about the ethical implications of this work, due to it relying on previous works that already addressed the ethical implications of using the microaggregation problem. I would suggest the authors add a small paragraph discussing this at the end of the paper (discuss further the ability of the microaggregation to ensure some privacy measures).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0JjP1wMtYl", "reviewer": "Reviewer_yZTt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. The main problem of interest, namely univariate microaggregation, is well-motivated and well-studied in prior literature. Moreover, in the regime where $k$ is large, the obtained improvement in the time complexity can be significant, which is also reflected in the experiments. From a technical standpoint, the approach is non-trivial and combines several interesting ideas starting from the connection with the least weight subsequence problem. Although many of the underlying ideas have been used before, I believe that the overall approach is technically novel and interesting. The main body of the paper does a nice job at explaining adequately the key ideas in the proofs. The writing overall is reasonable and the paper is well-organized. To my knowledge, all relevant papers have been discussed.\n\nWeaknesses. I believe that some crucial aspects of the paper's focus require further justification. The improvement in performance, both in theory and in the experimental results, depends crucially on how large parameter $k$ is. Is it not clear to me how large that parameter is in practical applications; perhaps taking $k$ to be reasonably small suffices for most purposes, in which case the theoretical bounds become rather vacuous (in light of prior work). Perhaps the authors can comment on how large $k$ should be thought of compared to $n$. Taking a step back, it is not even entirely clear how significant the refinement in the time complexity is for a problem such as microaggression; it is an offline problem in which reducing the running time by a small factor does not seem to be particularly consequential for most purposes; again, this depends on the specific applications the paper is targeting, which I feel is not discussed enough. Remaining on the motivation of the paper, it is also a significant caveat that the paper focuses only on the univariate case, which significantly limits the scope of the paper, although this has been acknowledged by the authors. Moreover, the experimental results are not entirely convincing. In particular, experimenting only on data generated under the specific process described in the paper can lead to misleading implications. Perhaps the authors can experiment with some real available data instead of creating such a synthetic dataset. \n\nBesides the issues above, it is not clear whether a machine learning venue is suited for this paper. I feel that both the techniques and the results will be more relevant to a different venue.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers the problem of microaggregation whereby data points are grouped into clusters of at least k points in order to guarantee k-anonymity---a type of privacy guarantee. In particular, the paper improves the time complexity for performing univariate microaggregation from $O(kn)$ to $O(n)$ on sorted data. The approach consists of casting the problem as an instance of the so-called concave last weight subsequence problem and works for several cost functions used for univariate microaggregation. Moreover, the claimed improvement in the asymptotic complexity is also reflected in some experiments.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "If possible, the authors should expand on the motivation and the significance of the results in the context of my comments above. It would also benefit the paper if further experiments with more realistic data were included.\n\nSome minor comments:\n\n- On 3 occasions you write \"we proof\" which is incorrect.\n- Page 20: there are issues with space before citations.\n- There are some missing punctuation marks in the equations of the appendix.", "broader_impact_concerns": "No concerns regarding ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "aIWbTcOKHm", "reviewer": "Reviewer_XfgC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper proposed a novel optimal univariate microaggregation, which offers better time complexity.\nThe equation and analysis are easy to follow.\n\n\nWeaknesses:\nThe data used for the experiment is not clear.  The claim for Real-world improvement does not make sense because this paper uses synthetic data. Where did you get one million reals?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides an optimal univariate microaggregation on sorted data in O(n) time and space, which is better than prior work regarding time complexity. Experiments show performance improvement.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Some clarifications needed:\n\nThis paper uses synthetic data and claims it is a real-world setting. How do you define the real-world setting for your experiment? \n\nCan you explain your experiment setting for Figures 4 and 5? Did you get the plot by running the experiment once or multiple times? Are you using the top results or the average result?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Requested changes:

My first point is that differential privacy is not mentioned anywhere in the paper. DP is the golden standard of privacy in the ML community, so I think it would be appropriate to have some discussion on how the $k$-anonymity type of protection the microaggregation gives would relate to the privacy protection given by DP. 

In the conclusions it is written that: "It is well known, that the privacy concept of k-anonymity may provide insufficient protection if for example the confidential attributes are not sufficiently diverse. Caution should thus be taken if k-anonymity, or microaggregation to achieve k-anonymity, is applied in practice." I think it would make sense to add DP e.g. there.

Please add some discussion on how the microaggregation technique is useful in ML. Here are few example questions that I think could be addressed: How would the privacy guarantees given by microaggregation be useful in ML? What are the pros / cons when compared to ML models trained with DP guarantees?

It was also commented by reviewers JNUo and yZTt that the method seems to be restricted to univariate data. There has been an addition of an experiment where the method is used for projected multivariate data, however it is difficult to judge based on the results how well the method fits to the multivariate case (also because the method works well for one of the datasets, the EIA dataset, but not for the other one, the Tarragona dataset, see Fig. 6). If possible add a comparison to a method designed for multivariate data, such as the one in

Domingo-Ferrer, J., Sebé, F., & Solanas, A. (2008). A polynomial-time approximation to optimal multivariate microaggregation. Computers & Mathematics with Applications, 55(4), 714-732.

Please try to also polish the new material on the multivariate experiment.
Decision: Accept (poster)