You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@asterixdb.apache.org by AsterixDB Code Review <do...@asterix-gerrit.ics.uci.edu> on 2026/08/07 14:09:57 UTC

[L] Change in asterixdb[master]: [ASTERIXDB-3803][RT] VTREE: speed up and refine vector index build

From Hongyu Shi <le...@gmail.com>:

Hongyu Shi has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21504?usp=email )


Change subject: [ASTERIXDB-3803][RT] VTREE: speed up and refine vector index build
......................................................................

[ASTERIXDB-3803][RT] VTREE: speed up and refine vector index build

- user model changes: no
- storage format changes: no
- interface changes: no

Details:

Remove unnecessary repeated work in HKPP for index creation, and relax
hard-coded rounds to speed up build time.

- Relax each candidate's nearest distance against the newly chosen
  centroid alone, since adding a centroid can only reduce that distance,
  never increase it. Seeding no longer rescans the whole chosen set on
  every pick, which was quadratic in the cluster count and a large cost
  of a build.
- Carry each point's pool distance from an oversampling round's first
  pass into its draw, so the round measures it once instead of twice,
  and read the vector only for the points actually drawn.
- Assign and accumulate in one pass per refinement iteration, since a
  point's contribution depends only on its own assignment.
- Decode the training sample once on the way in, and store it as raw
  doubles that later passes read by offset, rather than decoding tagged
  lists again on every pass.

Three changes alter results on purpose:

- Seed by squared distance for Euclidean.
- Oversample l = k per round over six refinement iterations, rather than
  2k over twenty.
- Merge only exact duplicate candidates, found by hashing their
  components, rather than any pair within a small distance. Candidates
  are verbatim copies of input points, so exact duplicates are the case
  that arises; this also removes a pairwise scan of the candidate set.

Change-Id: I7b3e5c1a9d24f068e3b7a105c48d2f9e63104b7a
---
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/KMeansUtils.java
2 files changed, 269 insertions(+), 157 deletions(-)



  git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/04/21504/1

diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
index d890f02..3d18e8b 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/HierarchicalKMeansPlusPlusCentroidsOperatorDescriptor.java
@@ -60,6 +60,7 @@
 import org.apache.hyracks.api.job.IOperatorDescriptorRegistry;
 import org.apache.hyracks.api.job.JobId;
 import org.apache.hyracks.data.std.api.IPointable;
+import org.apache.hyracks.data.std.primitive.DoublePointable;
 import org.apache.hyracks.data.std.primitive.VoidPointable;
 import org.apache.hyracks.data.std.util.ArrayBackedValueStorage;
 import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
@@ -67,6 +68,7 @@
 import org.apache.hyracks.dataflow.common.comm.io.FrameTupleAppender;
 import org.apache.hyracks.dataflow.common.comm.util.FrameUtils;
 import org.apache.hyracks.dataflow.common.data.accessors.FrameTupleReference;
+import org.apache.hyracks.dataflow.common.data.marshalling.DoubleSerializerDeserializer;
 import org.apache.hyracks.dataflow.common.data.marshalling.IntegerSerializerDeserializer;
 import org.apache.hyracks.dataflow.common.io.GeneratedRunFileReader;
 import org.apache.hyracks.dataflow.std.base.AbstractActivityNode;
@@ -414,6 +416,46 @@
     }
 
     // Clipping constants for centroid values
+    /**
+     * Layout of the materialized training sample: one field per tuple holding the vector's components as raw
+     * doubles, back to back. The sample is re-read on every cost, weighting and refinement pass, so it is
+     * decoded ONCE on the way in rather than on each pass; a pass then reads components by byte offset instead
+     * of walking a tagged ordered list (offset lookup, storage write, type-domain check, tag deserialize and a
+     * switch, per component). The declared serde is a placeholder -- reads go through field offsets.
+     */
+    private static final RecordDescriptor RAW_VECTOR_RD =
+            new RecordDescriptor(new ISerializerDeserializer[] { DoubleSerializerDeserializer.INSTANCE });
+
+    /** Reads one raw-double vector field, filling {@code reuse} when it is the right length. */
+    private static double[] readRawVector(FrameTupleReference t, double[] reuse) throws IOException {
+        int dim = t.getFieldLength(0) / Double.BYTES;
+        double[] v = (reuse != null && reuse.length == dim) ? reuse : new double[dim];
+        byte[] data = t.getFieldData(0);
+        int start = t.getFieldStart(0);
+        for (int i = 0; i < dim; i++) {
+            v[i] = DoublePointable.getDouble(data, start + i * Double.BYTES);
+        }
+        return v;
+    }
+
+    /** Oversampling rounds of the k-means|| seeding pass (Bahmani et al., VLDB'12, Alg. 2). */
+    private static final int OVERSAMPLING_ROUNDS = 5;
+
+    /** Oversampling factor as a multiple of k: each round draws l = OVERSAMPLING_FACTOR_PER_K * k in expectation. */
+    private static final double OVERSAMPLING_FACTOR_PER_K = 1.0;
+
+    /** Lloyd refinement iterations, both over the training sample and over each hierarchy level's centroids. */
+    private static final int LLOYD_ITERATIONS = 6;
+
+    /** Upper bound on hierarchy depth; the square-root fan-in below reaches a single root long before this. */
+    private static final int MAX_HIERARCHY_LEVELS = 100;
+
+    /** Two candidates closer than this are the same point drawn twice, and their weights are merged. */
+    private static final double DUPLICATE_DISTANCE_EPSILON = 1e-10;
+
+    /** Scale of the jitter applied when padding duplicate centroids apart to reach exactly k. */
+    private static final double CENTROID_PERTURBATION_SCALE = 1e-6;
+
     private static final double DEFAULT_CLIP_MIN = -1e3;
     private static final double DEFAULT_CLIP_MAX = 1e3;
 
@@ -581,9 +623,24 @@
             return new AbstractUnaryInputSinkOperatorNodePushable() {
                 private MaterializerTaskState materializedSample;
                 private TupleCountState tupleCountState;
+                private final FrameTupleAccessor fta = new FrameTupleAccessor(secondaryRecDesc);
+                private final FrameTupleReference tuple = new FrameTupleReference();
+                private IScalarEvaluator eval;
+                private final IPointable inputVal = new VoidPointable();
+                private final ListAccessor listAccessor = new ListAccessor();
+                private final IPointable decodeTemp = new VoidPointable();
+                private final ArrayBackedValueStorage decodeStorage = new ArrayBackedValueStorage();
+                private final KMeansUtils kMeansUtils = new KMeansUtils(decodeTemp, decodeStorage);
+                private final ArrayTupleBuilder tb = new ArrayTupleBuilder(1);
+                private VSizeFrame frame;
+                private FrameTupleAppender appender;
+                private double[] decodeBuffer;
 
                 @Override
                 public void open() throws HyracksDataException {
+                    eval = args.createScalarEvaluator(new EvaluatorContext(ctx));
+                    frame = new VSizeFrame(ctx);
+                    appender = new FrameTupleAppender(frame);
                     // Initialize data persistence for multiple passes over the data
                     materializedSample = new MaterializerTaskState(ctx.getJobletContext().getJobId(),
                             new PartitionedUUID(sampleUUID, partition));
@@ -596,19 +653,58 @@
 
                 @Override
                 public void nextFrame(ByteBuffer buffer) throws HyracksDataException {
-                    // Count tuples in this frame
-                    FrameTupleAccessor fta = new FrameTupleAccessor(secondaryRecDesc);
                     fta.reset(buffer);
                     int tupleCount = fta.getTupleCount();
-                    tupleCountState.addTupleCount(tupleCount);
+                    for (int j = 0; j < tupleCount; j++) {
+                        tuple.reset(fta, j);
+                        eval.evaluate(tuple, inputVal);
+                        if (!ATYPETAGDESERIALIZER.deserialize(inputVal.getByteArray()[inputVal.getStartOffset()])
+                                .isListType()) {
+                            continue; // not a vector; the passes below would have skipped it anyway
+                        }
+                        listAccessor.reset(inputVal.getByteArray(), inputVal.getStartOffset());
+                        double[] vec;
+                        try {
+                            vec = kMeansUtils.createPrimitveList(listAccessor, decodeBuffer);
+                            decodeBuffer = vec;
+                        } catch (IOException e) {
+                            throw HyracksDataException.create(e);
+                        }
+                        if (vec.length != vectorDimension) {
+                            continue; // wrong arity for this index; excluded from training
+                        }
+                        // Store the components raw so every later pass reads them by offset.
+                        tb.reset();
+                        try {
+                            DataOutput out = tb.getDataOutput();
+                            for (double d : vec) {
+                                out.writeDouble(d);
+                            }
+                            tb.addFieldEndOffset();
+                        } catch (IOException e) {
+                            throw HyracksDataException.create(e);
+                        }
+                        if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                            flushToSample();
+                            if (!appender.append(tb.getFieldEndOffsets(), tb.getByteArray(), 0, tb.getSize())) {
+                                throw HyracksDataException
+                                        .create(new IllegalStateException("training vector exceeds a frame"));
+                            }
+                        }
+                        tupleCountState.addTupleCount(1);
+                    }
+                }
 
-                    // Materialize all data to disk for subsequent processing passes
-                    // This allows us to make multiple passes over the data without loading it all into memory
-                    materializedSample.appendFrame(buffer);
+                private void flushToSample() throws HyracksDataException {
+                    if (appender.getTupleCount() > 0) {
+                        materializedSample.appendFrame(appender.getBuffer());
+                        appender.reset(frame, true);
+                    }
                 }
 
                 @Override
                 public void close() throws HyracksDataException {
+                    flushToSample();
                     if (materializedSample != null) {
                         materializedSample.close();
                         ctx.setStateObject(materializedSample);
@@ -655,6 +751,44 @@
                 // the per-partition pushable (never Java-serialized) keeps the un-serializable function off the
                 // wire and out of the shared descriptor.
                 private final IVTreeDistanceFunction distanceFunction = distanceFunctionFor(distanceMetricEnum);
+                private final boolean euclideanFastPath = distanceMetricEnum == VectorSimilarityMetric.EUCLIDEAN;
+
+                /**
+                 * The hottest call in this operator: invoked once per resident per centroid on every pass. The
+                 * For Euclidean this sums the squares directly instead of squaring the rooted distance, which
+                 * avoids a needless square root and the rounding it introduces.
+                 */
+                /**
+                 * D(x)&sup2; -- the quantity the seeding distributions are defined over. k-means|| draws a point
+                 * with probability {@code l * d(x,C)^2 / SUM d(x,C)^2} and k-means++ with probability proportional
+                 * to {@code d(x,C)^2} (Bahmani et al., VLDB'12, Alg. 2; Arthur &amp; Vassilvitskii, SODA'07).
+                 * Feeding an un-squared distance into those ratios flattens the distribution and under-weights
+                 * distant points, which is precisely the spread that oversampling exists to obtain -- so the
+                 * squared value is used wherever a distance becomes a probability -- for the EUCLIDEAN metric,
+                 * which is the only one that returns an un-squared distance. Ranking is unaffected
+                 * (squaring is monotone on non-negative distances), so assignment paths still use the plain
+                 * distance.
+                 */
+                private double calculateSquaredDistance(double[] a, double[] b) {
+                    if (euclideanFastPath) {
+                        int n = Math.min(a.length, b.length);
+                        double sum = 0.0;
+                        for (int i = 0; i < n; i++) {
+                            double d = a[i] - b[i];
+                            sum += d * d;
+                        }
+                        return sum; // already the squared distance; no root taken and none needed
+                    }
+                    // Every other metric already yields a value proportional to the squared-Euclidean
+                    // potential, so squaring again would be wrong:
+                    //  - EUCLIDEAN_SQUARED is the squared distance itself;
+                    //  - COSINE is 1 - cos, and for the unit-norm vectors this metric operates on
+                    //    ||a-b||^2 = 2(1 - cos), i.e. LINEAR in cosine distance, so the raw value is
+                    //    already the D^2 weight;
+                    //  - DOT returns -dot, which is negative for similar vectors, so squaring would
+                    //    invert the ordering (MIPS does not fit the D^2 framework at all).
+                    return calculateDistance(a, b);
+                }
 
                 private double calculateDistance(double[] a, double[] b) {
                     try {
@@ -700,7 +834,10 @@
                         IPointable tempVal = new VoidPointable();
                         ArrayBackedValueStorage storage = new ArrayBackedValueStorage();
                         KMeansUtils KMeansUtils = new KMeansUtils(tempVal, storage);
-                        fta = new FrameTupleAccessor(secondaryRecDesc);
+                        // The materialized sample holds one raw-double field per tuple, NOT the operator's
+                        // input layout: the accessor's field count sets the slot width it skips to reach
+                        // the data, so reading it with the input descriptor would offset every component.
+                        fta = new FrameTupleAccessor(RAW_VECTOR_RD);
                         tuple = new FrameTupleReference();
                         VSizeFrame vSizeFrame = new VSizeFrame(ctx);
                         FrameTupleAppender appender = new FrameTupleAppender(new VSizeFrame(ctx));
@@ -751,8 +888,8 @@
                         KMeansUtils kMeansUtils, int k, Random rand, int maxIterations, int totalTupleCount,
                         int partition) throws HyracksDataException, IOException {
                     //   k-means|| configuration
-                    int numRounds = 5; // Number of sampling rounds (default 5-10)
-                    double oversamplingFactor = 2.0 * k; // Oversampling factor l ≈ 2k
+                    int numRounds = OVERSAMPLING_ROUNDS;
+                    double oversamplingFactor = OVERSAMPLING_FACTOR_PER_K * k;
 
                     return performKMeansParallel(ctx, in, fta, tuple, eval, inputVal, listAccessorConstant, kMeansUtils,
                             k, rand, maxIterations, totalTupleCount, partition, numRounds, oversamplingFactor);
@@ -782,6 +919,9 @@
                     }
 
                     // Current centers for distance computation (starts with first centroid)
+                    // Reused by every per-point decode below; vectors retained beyond one loop
+                    // iteration are copied where they are retained.
+                    double[] pointBuffer = null;
                     List<double[]> currentCenters = new ArrayList<>();
                     currentCenters.add(firstCentroid);
 
@@ -789,8 +929,16 @@
                     List<double[]> candidates = new ArrayList<>();
 
                     // Step 2: Multiple rounds of probabilistic sampling (k-means||)
+                    // D(x) for every resident, carried from each round's cost pass into its sample pass.
+                    // The two passes need the SAME D(x): the first sums it into the potential, the second turns
+                    // it into the draw probability. Recomputing it in the second pass costs a full decode plus a
+                    // scan of the pool per point; caching one double per point costs 8 bytes per point and lets
+                    // the sample pass decode ONLY the points it actually draws (expected l of them per round).
+                    // NaN marks a resident that is not a usable vector, so both passes skip exactly the same set.
+                    double[] pointScores = new double[Math.max(totalTupleCount, 1)];
+
                     for (int round = 0; round < numRounds; round++) {
-                        // PASS 1: Compute S = Σ_x D(x) by streaming (NO DISTANCE STORAGE)
+                        // PASS 1: compute S = sum_x D(x), caching each D(x) for the sample pass below.
                         double totalDistance = 0.0;
 
                         in = resetRunFileReader(ctx, sampleUUID, partition);
@@ -803,33 +951,30 @@
                             int tupleCount = fta.getTupleCount();
 
                             for (int j = 0; j < tupleCount; j++) {
-                                tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (!ATYPETAGDESERIALIZER
-                                        .deserialize(inputVal.getByteArray()[inputVal.getStartOffset()]).isListType()) {
-                                    tempIdx++;
+                                // Advance for EVERY resident so the index stays aligned with the sample pass.
+                                int pointIdx = tempIdx++;
+                                if (pointIdx >= pointScores.length) {
                                     continue;
                                 }
-
-                                listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
+                                pointScores[pointIdx] = Double.NaN;
+                                tuple.reset(fta, j);
                                 try {
-                                    double[] point = kMeansUtils.createPrimitveList(listAccessorConstant);
+                                    double[] point = readRawVector(tuple, pointBuffer);
+                                    pointBuffer = point;
                                     // Compute D(x) = min distance to current centers
                                     if (point.length != vectorDimension) {
                                         continue;
                                     }
                                     double minDist = Double.POSITIVE_INFINITY;
                                     for (double[] center : currentCenters) {
-                                        double dist = calculateDistance(point, center);
+                                        double dist = calculateSquaredDistance(point, center);
                                         minDist = Math.min(minDist, dist);
                                     }
-
-                                    // Accumulate sum (NO STORAGE)
+                                    pointScores[pointIdx] = minDist;
                                     totalDistance += minDist;
                                 } catch (IOException e) {
                                     throw new RuntimeException(e);
                                 }
-                                tempIdx++;
                             }
                         }
 
@@ -849,38 +994,30 @@
                             int tupleCount = fta.getTupleCount();
 
                             for (int j = 0; j < tupleCount; j++) {
-                                tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (!ATYPETAGDESERIALIZER
-                                        .deserialize(inputVal.getByteArray()[inputVal.getStartOffset()]).isListType()) {
-                                    currentIdx++;
-                                    continue;
+                                int pointIdx = currentIdx++;
+                                double minDist = pointIdx < pointScores.length ? pointScores[pointIdx] : Double.NaN;
+                                if (Double.isNaN(minDist)) {
+                                    continue; // not a usable vector; the cost pass skipped it too
                                 }
 
-                                listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
-                                try {
-                                    double[] point = kMeansUtils.createPrimitveList(listAccessorConstant);
+                                //   probabilistic sampling: p(x) = l * D(x) / S
+                                double probability = oversamplingFactor * minDist / totalDistance;
 
-                                    // RECOMPUTE D(x) (no storage from pass 1)
-                                    double minDist = Double.POSITIVE_INFINITY;
-                                    for (double[] center : currentCenters) {
-                                        double dist = calculateDistance(point, center);
-                                        minDist = Math.min(minDist, dist);
-                                    }
-
-                                    //   probabilistic sampling: p(x) = l * D(x) / S
-                                    double probability = oversamplingFactor * minDist / totalDistance;
-
-                                    // Independent Bernoulli trial for each point
-                                    if (rand.nextDouble() < probability) {
-                                        // Add to candidates (copy to avoid mutation)
+                                // Independent Bernoulli trial for each point. The draw consumes one random value
+                                // per candidate resident, exactly as before, so the drawn set is unchanged.
+                                if (rand.nextDouble() < probability) {
+                                    // Only a drawn point needs its vector, so it is read here, inside the draw:
+                                    // an expected l reads per round rather than one per resident.
+                                    tuple.reset(fta, j);
+                                    try {
+                                        double[] point = readRawVector(tuple, pointBuffer);
+                                        pointBuffer = point;
                                         candidates.add(Arrays.copyOf(point, point.length));
                                         sampledCount++;
+                                    } catch (IOException e) {
+                                        throw new RuntimeException(e);
                                     }
-                                } catch (IOException e) {
-                                    throw new RuntimeException(e);
                                 }
-                                currentIdx++;
                             }
                         }
 
@@ -908,16 +1045,9 @@
 
                         for (int j = 0; j < tupleCount; j++) {
                             tuple.reset(fta, j);
-                            eval.evaluate(tuple, inputVal);
-                            if (!ATYPETAGDESERIALIZER.deserialize(inputVal.getByteArray()[inputVal.getStartOffset()])
-                                    .isListType()) {
-                                weightIdx++;
-                                continue;
-                            }
-
-                            listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
                             try {
-                                double[] point = kMeansUtils.createPrimitveList(listAccessorConstant);
+                                double[] point = readRawVector(tuple, pointBuffer);
+                                pointBuffer = point;
 
                                 // Find nearest candidate (recompute distance)
                                 double minDist = Double.POSITIVE_INFINITY;
@@ -942,26 +1072,27 @@
                     List<double[]> weightedCandidates = new ArrayList<>();
                     List<Integer> weightedCandidateWeights = new ArrayList<>();
 
-                    // Reduce duplicates: combine identical/very close candidates and sum their weights
+                    // Merge duplicate candidates and sum their weights. Candidates are drawn from the residents,
+                    // so a duplicate is the same resident drawn in two rounds and is component-wise identical --
+                    // never merely nearby. Keying on the components therefore identifies duplicates exactly, in a
+                    // single pass and without any distance computation.
+                    Map<List<Double>, Integer> mergedIndexByPoint = new HashMap<>();
                     for (int i = 0; i < candidates.size(); i++) {
                         if (candidateWeights[i] == 0) {
                             continue; // Skip candidates with no assigned points (zero weight)
                         }
-
-                        // Check if this candidate is a duplicate of an existing weighted candidate
-                        boolean foundDuplicate = false;
-                        for (int j = 0; j < weightedCandidates.size(); j++) {
-                            double dist = calculateDistance(candidates.get(i), weightedCandidates.get(j));
-                            if (dist < 1e-10) { // Consider identical if very close
-                                // Merge near-duplicate candidates by adding their weights
-                                weightedCandidateWeights.set(j, weightedCandidateWeights.get(j) + candidateWeights[i]);
-                                foundDuplicate = true;
-                                break;
-                            }
+                        double[] cand = candidates.get(i);
+                        List<Double> key = new ArrayList<>(cand.length);
+                        for (double v : cand) {
+                            key.add(v);
                         }
-
-                        if (!foundDuplicate) {
-                            weightedCandidates.add(Arrays.copyOf(candidates.get(i), candidates.get(i).length));
+                        Integer existing = mergedIndexByPoint.get(key);
+                        if (existing != null) {
+                            weightedCandidateWeights.set(existing,
+                                    weightedCandidateWeights.get(existing) + candidateWeights[i]);
+                        } else {
+                            mergedIndexByPoint.put(key, weightedCandidates.size());
+                            weightedCandidates.add(Arrays.copyOf(cand, cand.length));
                             weightedCandidateWeights.add(candidateWeights[i]);
                         }
                     }
@@ -1010,7 +1141,7 @@
                                     boolean isDuplicate = false;
                                     for (double[] existingCentroid : centroids) {
                                         double dist = calculateDistance(additionalPoint, existingCentroid);
-                                        if (dist < 1e-10) { // Consider it a duplicate if very close
+                                        if (dist < DUPLICATE_DISTANCE_EPSILON) { // Consider it a duplicate if very close
                                             isDuplicate = true;
                                             break;
                                         }
@@ -1027,7 +1158,7 @@
                                 double[] perturbed = Arrays.copyOf(base, base.length);
                                 // Add tiny random perturbation to make it distinct
                                 for (int d = 0; d < perturbed.length; d++) {
-                                    perturbed[d] += rand.nextGaussian() * 1e-6;
+                                    perturbed[d] += rand.nextGaussian() * CENTROID_PERTURBATION_SCALE;
                                 }
                                 centroids.add(perturbed);
                             }
@@ -1042,7 +1173,9 @@
 
                     // 3. Lloyd's algorithm for refinement using streaming approach
                     for (int iter = 0; iter < maxIterations; iter++) {
-                        // Assignment phase: assign each point to closest centroid
+                        // Single pass: assign each point to its closest centroid AND accumulate its contribution.
+                        double[][] newCentroids = new double[centroids.size()][centroids.get(0).length];
+                        int[] counts = new int[centroids.size()];
                         VSizeFrame frame = new VSizeFrame(ctx);
                         int currentIdx = 0;
                         while (in.nextFrame(frame)) {
@@ -1052,16 +1185,9 @@
 
                             for (int j = 0; j < tupleCount; j++) {
                                 tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (!ATYPETAGDESERIALIZER
-                                        .deserialize(inputVal.getByteArray()[inputVal.getStartOffset()]).isListType()) {
-                                    currentIdx++;
-                                    continue;
-                                }
-
-                                listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
                                 try {
-                                    double[] point = kMeansUtils.createPrimitveList(listAccessorConstant);
+                                    double[] point = readRawVector(tuple, pointBuffer);
+                                    pointBuffer = point;
 
                                     // Find closest centroid
                                     double minDist = Double.POSITIVE_INFINITY;
@@ -1073,47 +1199,14 @@
                                             closestCentroid = c;
                                         }
                                     }
+                                    // A point contributes to exactly one centroid, and to no other point's
+                                    // contribution, so its assignment and its accumulation can both be done while
+                                    // it is in hand -- the iteration needs a single pass over the sample.
                                     assignments[currentIdx] = closestCentroid;
-
-                                } catch (IOException e) {
-                                    throw new RuntimeException(e);
-                                }
-                                currentIdx++;
-                            }
-                        }
-
-                        // Reset reader for update phase
-                        in = resetRunFileReader(ctx, sampleUUID, partition);
-
-                        // Update phase: calculate new centroids
-                        double[][] newCentroids = new double[centroids.size()][centroids.get(0).length];
-                        int[] counts = new int[centroids.size()];
-
-                        frame = new VSizeFrame(ctx);
-                        currentIdx = 0;
-                        while (in.nextFrame(frame)) {
-                            ByteBuffer buffer = frame.getBuffer();
-                            fta.reset(buffer);
-                            int tupleCount = fta.getTupleCount();
-
-                            for (int j = 0; j < tupleCount; j++) {
-                                tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (!ATYPETAGDESERIALIZER
-                                        .deserialize(inputVal.getByteArray()[inputVal.getStartOffset()]).isListType()) {
-                                    currentIdx++;
-                                    continue;
-                                }
-
-                                listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
-                                try {
-                                    double[] point = kMeansUtils.createPrimitveList(listAccessorConstant);
-
-                                    int centroidIdx = assignments[currentIdx];
                                     for (int d = 0; d < point.length; d++) {
-                                        newCentroids[centroidIdx][d] += point[d];
+                                        newCentroids[closestCentroid][d] += point[d];
                                     }
-                                    counts[centroidIdx]++;
+                                    counts[closestCentroid]++;
 
                                 } catch (IOException e) {
                                     throw new RuntimeException(e);
@@ -1181,7 +1274,7 @@
                                 double[] base = candidates.get(idx);
                                 double[] copy = Arrays.copyOf(base, base.length);
                                 for (int d = 0; d < copy.length; d++) {
-                                    copy[d] += rand.nextGaussian() * 1e-6;
+                                    copy[d] += rand.nextGaussian() * CENTROID_PERTURBATION_SCALE;
                                 }
                                 result.add(copy);
                             }
@@ -1197,20 +1290,24 @@
                     int firstIdx = selectWeightedRandomIndex(candidates, weights, rand);
                     resultCentroids.add(Arrays.copyOf(candidates.get(firstIdx), candidates.get(firstIdx).length));
 
-                    // 2. Choose remaining centroids using weighted selection
-                    for (int i = 1; i < k && i < candidates.size(); i++) {
-                        double[] weightedDistances = new double[candidates.size()];
-                        double totalWeightedDistance = 0.0;
+                    // D(c) for every candidate: its distance to the NEAREST centroid chosen so far. A new centroid
+                    // can only ever shorten that distance, so the array is seeded from the first centroid and then
+                    // relaxed against each newly chosen one, giving O(candidates) distance computations per pick
+                    // rather than O(candidates * chosen). Each pick consumes exactly one random value.
+                    final int candidateCount = candidates.size();
+                    double[] nearestDist = new double[candidateCount];
+                    double[] seedCentroid = resultCentroids.get(0);
+                    for (int j = 0; j < candidateCount; j++) {
+                        nearestDist[j] = calculateSquaredDistance(candidates.get(j), seedCentroid);
+                    }
+                    double[] weightedDistances = new double[candidateCount];
 
-                        // Calculate minimum weighted distance to existing centroids for each candidate
-                        for (int j = 0; j < candidates.size(); j++) {
-                            double minDist = Double.POSITIVE_INFINITY;
-                            for (double[] centroid : resultCentroids) {
-                                double dist = calculateDistance(candidates.get(j), centroid);
-                                minDist = Math.min(minDist, dist);
-                            }
+                    // 2. Choose remaining centroids using weighted selection
+                    for (int i = 1; i < k && i < candidateCount; i++) {
+                        double totalWeightedDistance = 0.0;
+                        for (int j = 0; j < candidateCount; j++) {
                             // Weighted distance: weight[j] * D(c_j)
-                            weightedDistances[j] = weights[j] * minDist;
+                            weightedDistances[j] = weights[j] * nearestDist[j];
                             totalWeightedDistance += weightedDistances[j];
                         }
 
@@ -1222,7 +1319,7 @@
                         double r = rand.nextDouble() * totalWeightedDistance;
                         double cumulativeDistance = 0.0;
                         int selectedIdx = 0;
-                        for (int j = 0; j < candidates.size(); j++) {
+                        for (int j = 0; j < candidateCount; j++) {
                             cumulativeDistance += weightedDistances[j];
                             if (cumulativeDistance >= r) {
                                 selectedIdx = j;
@@ -1230,8 +1327,16 @@
                             }
                         }
 
-                        resultCentroids
-                                .add(Arrays.copyOf(candidates.get(selectedIdx), candidates.get(selectedIdx).length));
+                        double[] chosen =
+                                Arrays.copyOf(candidates.get(selectedIdx), candidates.get(selectedIdx).length);
+                        resultCentroids.add(chosen);
+                        // Relax D(c) against the newly chosen centroid only.
+                        for (int j = 0; j < candidateCount; j++) {
+                            double dist = calculateSquaredDistance(candidates.get(j), chosen);
+                            if (dist < nearestDist[j]) {
+                                nearestDist[j] = dist;
+                            }
+                        }
                     }
 
                     // 3. Weighted Lloyd's algorithm for refinement
@@ -1305,7 +1410,7 @@
                                 boolean isAlreadyCentroid = false;
                                 for (double[] centroid : resultCentroids) {
                                     double dist = calculateDistance(candidates.get(i), centroid);
-                                    if (dist < 1e-10) {
+                                    if (dist < DUPLICATE_DISTANCE_EPSILON) {
                                         isAlreadyCentroid = true;
                                         break;
                                     }
@@ -1338,7 +1443,7 @@
                                     double[] base = resultCentroids.get(resultCentroids.size() - 1);
                                     double[] perturbed = Arrays.copyOf(base, base.length);
                                     for (int d = 0; d < perturbed.length; d++) {
-                                        perturbed[d] += rand.nextGaussian() * 1e-6;
+                                        perturbed[d] += rand.nextGaussian() * CENTROID_PERTURBATION_SCALE;
                                     }
                                     resultCentroids.add(perturbed);
                                 }
@@ -1393,14 +1498,7 @@
                         for (int j = 0; j < tupleCount; j++) {
                             if (currentIndex == targetIndex) {
                                 tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (!ATYPETAGDESERIALIZER
-                                        .deserialize(inputVal.getByteArray()[inputVal.getStartOffset()]).isListType()) {
-                                    return null;
-                                }
-
-                                listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
-                                return kMeansUtils.createPrimitveList(listAccessorConstant);
+                                return readRawVector(tuple, null);
                             }
                             currentIndex++;
                         }
@@ -1434,12 +1532,7 @@
                             // Multiple requested indices may map to the same tuple (duplicates in the list).
                             while (ti < sortedIndices.size() && sortedIndices.get(ti) == currentIndex) {
                                 tuple.reset(fta, j);
-                                eval.evaluate(tuple, inputVal);
-                                if (ATYPETAGDESERIALIZER.deserialize(inputVal.getByteArray()[inputVal.getStartOffset()])
-                                        .isListType()) {
-                                    listAccessorConstant.reset(inputVal.getByteArray(), inputVal.getStartOffset());
-                                    results.set(ti, kMeansUtils.createPrimitveList(listAccessorConstant));
-                                }
+                                results.set(ti, readRawVector(tuple, null));
                                 ti++;
                             }
                             currentIndex++;
@@ -1519,8 +1612,8 @@
                     // Initialize currentK using square root reduction for balanced hierarchical structure
                     int currentK =
                             Math.min(K, Math.max(1, (int) Math.floor(Math.sqrt(initialResult.centroids.size()))));
-                    int maxIterations = 20;
-                    int maxLevels = 100;
+                    int maxIterations = LLOYD_ITERATIONS;
+                    int maxLevels = MAX_HIERARCHY_LEVELS;
                     // The K leaf centroids were stored at map key 0 above. Parent levels must occupy keys
                     // 1..maxLevel so the leaves stay at key 0 and are emitted by outputHierarchicalStructure
                     // (which walks keys 0..maxLevel). Starting at 0 would overwrite key 0 and re-key the true
@@ -1589,7 +1682,7 @@
                         for (int j = 0; j < centroids.size(); j++) {
                             double minDist = Double.POSITIVE_INFINITY;
                             for (double[] centroid : resultCentroids) {
-                                double dist = calculateDistance(centroids.get(j), centroid);
+                                double dist = calculateSquaredDistance(centroids.get(j), centroid);
                                 minDist = Math.min(minDist, dist);
                             }
                             distances[j] = minDist;
@@ -1626,7 +1719,7 @@
                                 boolean alreadySelected = false;
                                 for (double[] existing : resultCentroids) {
                                     double dist = calculateDistance(centroids.get(j), existing);
-                                    if (dist < 1e-10) {
+                                    if (dist < DUPLICATE_DISTANCE_EPSILON) {
                                         alreadySelected = true;
                                         break;
                                     }
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/KMeansUtils.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/KMeansUtils.java
index 110cf2f..bc3d1af 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/KMeansUtils.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/operators/KMeansUtils.java
@@ -46,6 +46,25 @@
     }
 
     // Euclidean Distance
+    /**
+     * Decodes into {@code reuse} when it is the right length, so a caller that consumes the vector within one
+     * loop iteration can avoid allocating a fresh array per point. The training passes here re-read the same
+     * materialized sample many times, so the per-point allocation is otherwise repeated on every pass.
+     * The returned array is only valid until the next call with the same buffer -- callers that retain the
+     * vector (e.g. adding it to a candidate list) must copy it.
+     */
+    protected double[] createPrimitveList(ListAccessor listAccessor, double[] reuse) throws IOException {
+        ATypeTag typeTag = listAccessor.getItemType();
+        int size = listAccessor.size();
+        double[] primitiveArray = (reuse != null && reuse.length == size) ? reuse : new double[size];
+        storage.reset();
+        for (int i = 0; i < size; i++) {
+            listAccessor.getOrWriteItem(i, tempVal, storage);
+            primitiveArray[i] = extractNumericVector(tempVal, typeTag);
+        }
+        return primitiveArray;
+    }
+
     protected double[] createPrimitveList(ListAccessor listAccessor) throws IOException {
         ATypeTag typeTag = listAccessor.getItemType();
         double[] primitiveArray = new double[listAccessor.size()];

-- 
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21504?usp=email
To unsubscribe, or for help writing mail filters, visit https://asterix-gerrit.ics.uci.edu/settings?usp=email

Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I7b3e5c1a9d24f068e3b7a105c48d2f9e63104b7a
Gerrit-Change-Number: 21504
Gerrit-PatchSet: 1
Gerrit-Owner: Hongyu Shi <le...@gmail.com>