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/09/28 15:53:09 UTC
[M] Change in asterixdb[master]: [WIP][NO ISSUE][STO] Apply DOT epsilon in 1-cos space
From Calvin Thomas Dani <ca...@gmail.com>:
Calvin Thomas Dani has uploaded this change for review. ( https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21918?usp=email )
Change subject: [WIP][NO ISSUE][STO] Apply DOT epsilon in 1-cos space
......................................................................
[WIP][NO ISSUE][STO] Apply DOT epsilon in 1-cos space
Hop ranking stays -dot. The multiplicative window used |closest| near 1
and probed almost every positive-IP list. Map hops to 1-cosθ so ε matches
cosine for normalized and raw queries.
Co-Authored-By: Grok 4.7 <no...@x.ai>
Change-Id: Ia5185306de310dc19c3d3bdb1ee878f8128baa35
Co-authored-by: Cursor <cu...@cursor.com>
---
M asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
A asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/utils/VTreeDotEpsilonWindowTest.java
M hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/api/IVTreeDistanceFunction.java
M hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/impls/VTreeSearchPredicate.java
M hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/utils/VTreeNavigationUtils.java
5 files changed, 141 insertions(+), 31 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb refs/changes/18/21918/1
diff --git a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
index 39b09b3..6ec552f 100644
--- a/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
+++ b/asterixdb/asterix-runtime/src/main/java/org/apache/asterix/runtime/utils/VectorDistanceCalculation.java
@@ -123,6 +123,11 @@
public double decodeAndApply(double[] query, byte[] bytes, int offset, int length) throws HyracksDataException {
return fusedDotDistance(query, bytes, offset, length, null);
}
+
+ @Override
+ public double toEpsilonDistance(double hopDistance, double queryNorm) {
+ return dotHopToEpsilonDistance(hopDistance, queryNorm);
+ }
}
public static double euclidean(double[] a, double[] b) {
@@ -203,6 +208,18 @@
}
/**
+ * Cosine-shaped ε coordinate for a DOT hop {@code -q·c} when centroids are unit:
+ * {@code 1 + hop/|q| = 1 − cosθ}. Ranking stays {@code -dot}; only the ε window uses this.
+ * A vanishing or non-finite {@code |q|} keeps the hop unchanged (zero query has no angle).
+ */
+ public static double dotHopToEpsilonDistance(double hopDistance, double queryNorm) {
+ if (queryNorm <= 1e-12 || !Double.isFinite(queryNorm) || !Double.isFinite(hopDistance)) {
+ return hopDistance;
+ }
+ return 1.0 + hopDistance / queryNorm;
+ }
+
+ /**
* Sum of squared differences between {@code query} and the vector encoded at {@code bytes[offset..]},
* decoding as it goes. {@code dst} receives the decoded vector, or may be {@code null} when the caller
* only wants the distance — the check is loop-invariant, so the JIT hoists it out and the store
diff --git a/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/utils/VTreeDotEpsilonWindowTest.java b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/utils/VTreeDotEpsilonWindowTest.java
new file mode 100644
index 0000000..f802d3d
--- /dev/null
+++ b/asterixdb/asterix-runtime/src/test/java/org/apache/asterix/runtime/utils/VTreeDotEpsilonWindowTest.java
@@ -0,0 +1,61 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.runtime.utils;
+
+import org.apache.hyracks.storage.am.vector.api.IVTreeDistanceFunction;
+import org.apache.hyracks.storage.am.vector.utils.VTreeNavigationUtils;
+import org.junit.Assert;
+import org.junit.Test;
+
+/**
+ * DOT ε must keep the cosine neighborhood (only list A) for both unit and scaled queries. Raw
+ * {@code -dot} ε keeps C as well.
+ */
+public class VTreeDotEpsilonWindowTest {
+
+ private static final double EPS = 0.75;
+ private static final IVTreeDistanceFunction DOT = VectorDistanceCalculation.DOT_DISTANCE_FN;
+ private static final IVTreeDistanceFunction COSINE = VectorDistanceCalculation.COSINE_DISTANCE_FN;
+
+ @Test
+ public void unitQueryDotWindowMatchesCosineAndDropsFarList() {
+ // A 0.99, B 0.97, C 0.40 — hops are -IP for DOT and 1-IP for cosine.
+ double closestDot = -0.99;
+ Assert.assertTrue(VTreeNavigationUtils.isWithinEpsilonWindow(-0.99, closestDot, EPS, DOT, 1.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(-0.97, closestDot, EPS, DOT, 1.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(-0.40, closestDot, EPS, DOT, 1.0));
+
+ double closestCos = 0.01;
+ Assert.assertTrue(VTreeNavigationUtils.isWithinEpsilonWindow(0.01, closestCos, EPS, COSINE, 1.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(0.03, closestCos, EPS, COSINE, 1.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(0.60, closestCos, EPS, COSINE, 1.0));
+ }
+
+ @Test
+ public void scaledQueryDotWindowStillDropsFarList() {
+ // Same angles, |q|=2: hop = -|q|cosθ. Naive -dot ε would keep C; 1-cos ε does not.
+ double closestDot = -1.98;
+ Assert.assertEquals(0.01, VectorDistanceCalculation.dotHopToEpsilonDistance(-1.98, 2.0), 1e-12);
+ Assert.assertTrue(VTreeNavigationUtils.isWithinEpsilonWindow(-1.98, closestDot, EPS, DOT, 2.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(-1.94, closestDot, EPS, DOT, 2.0));
+ Assert.assertFalse(VTreeNavigationUtils.isWithinEpsilonWindow(-0.80, closestDot, EPS, DOT, 2.0));
+ Assert.assertTrue("raw -dot window must still contain C — that is the bug being fixed",
+ -0.80 <= closestDot + Math.abs(closestDot) * EPS);
+ }
+}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/api/IVTreeDistanceFunction.java b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/api/IVTreeDistanceFunction.java
index ac18192..db4ce00 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/api/IVTreeDistanceFunction.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/api/IVTreeDistanceFunction.java
@@ -91,4 +91,14 @@
default double decodeAndApply(double[] query, byte[] bytes, int offset, int length) throws HyracksDataException {
return apply(query, DoubleArraySerializerDeserializer.read(bytes, offset, length));
}
+
+ /**
+ * Map a hop distance into the space where {@code closest + |closest|·ε} is a cosine-sized window.
+ * Cosine and L2 hops are already in that space (identity). DOT hops are {@code -q·c}; with unit
+ * spherical centroids that is {@code -|q|cosθ}, so this becomes {@code 1 - cosθ} after dividing
+ * by {@code queryNorm = |q|}.
+ */
+ default double toEpsilonDistance(double hopDistance, double queryNorm) {
+ return hopDistance;
+ }
}
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/impls/VTreeSearchPredicate.java b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/impls/VTreeSearchPredicate.java
index aa7e41f..ac8a538 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/impls/VTreeSearchPredicate.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/impls/VTreeSearchPredicate.java
@@ -129,8 +129,8 @@
/**
* Set the epsilon parameter (relative distance threshold for level-wise cross-pollination).
- * Clusters within {@code closestDistance + |closestDistance| * epsilon} — i.e. (1+epsilon)*d
- * for positive distances and (1-epsilon)*d for negative ones — will be explored via level-wise.
+ * Clusters within {@code closest + |closest|·epsilon} in {@code toEpsilonDistance} space are
+ * explored. Cosine/L2 use hop distance; DOT maps hops to {@code 1-cosθ} first.
*/
public void setEpsilon(double epsilon) {
this.epsilon = epsilon;
diff --git a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/utils/VTreeNavigationUtils.java b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/utils/VTreeNavigationUtils.java
index 3a0e8f6..650687b 100644
--- a/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/utils/VTreeNavigationUtils.java
+++ b/hyracks-fullstack/hyracks/hyracks-storage-am-vtree/src/main/java/org/apache/hyracks/storage/am/vector/utils/VTreeNavigationUtils.java
@@ -532,26 +532,37 @@
/**
* Multiplicative-epsilon distance threshold relative to {@code |closestDistance|}: yields
- * {@code (1+epsilon)*d} for positive {@code d} and {@code (1-epsilon)*d} for negative {@code d}
- * (negated dot product, where smaller is better). An additive {@code d+epsilon} form is a near
- * no-op for euclidean_squared / high-dim L2 where distances are O(10)-O(10^3), which collapses the
- * search to ~1 cluster regardless of nprobe/epsilon.
+ * {@code (1+epsilon)*d} for positive {@code d}. DOT hops are mapped with
+ * {@link IVTreeDistanceFunction#toEpsilonDistance} to {@code 1-cosθ} before this formula so the
+ * window matches cosine; cosine/L2 hops are already in that space.
*/
- private static double epsilonThreshold(double closestDistance, double epsilon) {
+ static double epsilonThreshold(double closestDistance, double epsilon) {
return closestDistance + Math.abs(closestDistance) * epsilon;
}
/**
+ * Whether {@code hopDistance} lies in the ε window of {@code closestHopDistance} after each hop
+ * is mapped through {@link IVTreeDistanceFunction#toEpsilonDistance}.
+ */
+ public static boolean isWithinEpsilonWindow(double hopDistance, double closestHopDistance, double epsilon,
+ IVTreeDistanceFunction distanceFunction, double queryNorm) {
+ if (epsilon <= 0.0) {
+ return true;
+ }
+ double closestEps = distanceFunction.toEpsilonDistance(closestHopDistance, queryNorm);
+ double hopEps = distanceFunction.toEpsilonDistance(hopDistance, queryNorm);
+ return hopEps <= epsilonThreshold(closestEps, epsilon);
+ }
+
+ /**
* Find close centroids using level-by-level cross-pollination with global sorting.
- * At each interior node, explores all children within closestDistance * (1 + epsilon)
- * (for positive distances) / closestDistance * (1 - epsilon) (for negative distances
- * such as negated dot product).
- * At leaf level, collects ALL centroids, then sorts globally and filters by epsilon.
+ * Interior children and the final leaf shortlist use {@link #isWithinEpsilonWindow} so DOT
+ * windows match cosine ({@code 1-cosθ}) while hop ranking stays {@code -dot}.
* <p>
* 1. Traverse tree using epsilon threshold at interior levels
* 2. Collect ALL reachable leaf centroids
- * 3. Sort globally by distance to query
- * 4. Filter by global closest distance + epsilon
+ * 3. Sort globally by hop distance to the query
+ * 4. Filter by the globally closest centroid's ε window
*
* @param bufferCache Buffer cache for page access
* @param fileId File ID for page identification
@@ -560,10 +571,8 @@
* @param leafFrameFactory Factory for creating leaf frames
* @param queryVector Query vector to find closest centroids for
* @param distanceFunction Distance function to use
- * @param epsilon Relative distance threshold (multiplicative). Threshold for level/global
- * pruning is computed as {@code closestDistance + |closestDistance| * epsilon},
- * i.e. (1+epsilon)*d for positive d and (1-epsilon)*d for negative d.
- * @return List of ClusterSearchResult containing all qualifying centroids, sorted by distance
+ * @param epsilon Relative distance threshold (multiplicative) in {@code toEpsilonDistance} space
+ * @return List of ClusterSearchResult containing all qualifying centroids, sorted by hop distance
* @throws HyracksDataException if any error occurs during traversal
*/
public static List<ClusterSearchResult> findCloseCentroidsLevelWiseGlobalSort(IBufferCache bufferCache, int fileId,
@@ -587,6 +596,7 @@
double[] queryVector, IVTreeDistanceFunction distanceFunction, double epsilon,
double[] quantizedQueryVector, IVTreeQuantizer quantizer) throws HyracksDataException {
+ double queryNorm = l2Norm(queryVector);
List<ClusterSearchResult> allCentroids = new ArrayList<>();
Set<Integer> visitedLeafPages = new HashSet<>();
Queue<VTreeLevelNode> queue = new ArrayDeque<>();
@@ -639,7 +649,7 @@
IVTreeInteriorFrame interiorFrame = (IVTreeInteriorFrame) interiorFrameFactory.createFrame();
interiorFrame.setPage(page);
queue.addAll(childrenWithinEpsilon(bufferCache, fileId, queryVector, node, interiorFrame,
- interiorFrameFactory, distanceFunction, epsilon));
+ interiorFrameFactory, distanceFunction, epsilon, queryNorm));
}
} finally {
@@ -657,7 +667,7 @@
allCentroids.sort(Comparator.comparingDouble(r -> r.distance));
// Phase 3: Apply epsilon threshold based on the globally closest centroid
- return applyGlobalEpsilonFilter(allCentroids, epsilon);
+ return applyGlobalEpsilonFilter(allCentroids, epsilon, distanceFunction, queryNorm);
}
/**
@@ -669,45 +679,57 @@
*/
private static List<VTreeLevelNode> childrenWithinEpsilon(IBufferCache bufferCache, int fileId,
double[] queryVector, VTreeLevelNode node, IVTreeInteriorFrame interiorFrame,
- ITreeIndexFrameFactory interiorFrameFactory, IVTreeDistanceFunction distanceFunction, double epsilon)
- throws HyracksDataException {
+ ITreeIndexFrameFactory interiorFrameFactory, IVTreeDistanceFunction distanceFunction, double epsilon,
+ double queryNorm) throws HyracksDataException {
List<VTreeChildCentroid> sortedChildren = collectAllChildCentroids(bufferCache, fileId, queryVector,
node.pageId(), interiorFrame, interiorFrameFactory, distanceFunction);
if (sortedChildren.isEmpty()) {
return List.of();
}
- double localThreshold = epsilonThreshold(sortedChildren.get(0).distance(), epsilon);
+ double closestHop = sortedChildren.get(0).distance();
List<VTreeLevelNode> nextLevel = new ArrayList<>();
for (VTreeChildCentroid child : sortedChildren) {
- if (child.distance() <= localThreshold) {
+ if (isWithinEpsilonWindow(child.distance(), closestHop, epsilon, distanceFunction, queryNorm)) {
nextLevel.add(new VTreeLevelNode(child.childPageId(), node.level() + 1));
} else {
- break; // Children are sorted, no more qualify
+ break; // hop-sorted; toEpsilonDistance is monotone in hop for DOT and identity metrics
}
}
return nextLevel;
}
/**
- * Phase 3 of level-wise search: given all collected centroids already sorted by distance ascending,
- * keep only those within the epsilon window of the globally closest centroid. Returns the input list
- * unchanged when {@code epsilon <= 0.0} (no filtering). Pure list operation — no page access.
+ * Phase 3 of level-wise search: given all collected centroids already sorted by hop distance
+ * ascending, keep only those within the ε window of the globally closest centroid. Returns the
+ * input list unchanged when {@code epsilon <= 0.0} (no filtering). Pure list operation — no page
+ * access.
*/
private static List<ClusterSearchResult> applyGlobalEpsilonFilter(List<ClusterSearchResult> sortedCentroids,
- double epsilon) {
+ double epsilon, IVTreeDistanceFunction distanceFunction, double queryNorm) {
if (epsilon <= 0.0) {
return sortedCentroids;
}
- double globalThreshold = epsilonThreshold(sortedCentroids.get(0).distance, epsilon);
+ double closestHop = sortedCentroids.get(0).distance;
List<ClusterSearchResult> filteredCentroids = new ArrayList<>();
for (ClusterSearchResult result : sortedCentroids) {
- if (result.distance <= globalThreshold) {
+ if (isWithinEpsilonWindow(result.distance, closestHop, epsilon, distanceFunction, queryNorm)) {
filteredCentroids.add(result);
} else {
- break; // Centroids are sorted, so we can break early
+ break;
}
}
return filteredCentroids;
}
+ private static double l2Norm(double[] queryVector) {
+ if (queryVector == null || queryVector.length == 0) {
+ return 0.0;
+ }
+ double sum = 0.0;
+ for (double x : queryVector) {
+ sum += x * x;
+ }
+ return Math.sqrt(sum);
+ }
+
}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/21918?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: Ia5185306de310dc19c3d3bdb1ee878f8128baa35
Gerrit-Change-Number: 21918
Gerrit-PatchSet: 1
Gerrit-Owner: Calvin Thomas Dani <ca...@gmail.com>