从共享角度位到有预算的候选检索 ​

任务起点与可运行材料 ​

本终点承接角度指纹理路随机超平面角度指纹Random hyperplane angular sketch · Random hyperplane fingerprint在共享超平面配置下把非零方向编码为规范位串，以失配比例估计归一化夹角，并区分固定对象保证与自适应重用。与LSH候选索引理路LSH 放大候选索引LSH amplification index · AND-OR locality-sensitive hashing index把独立基础碰撞组成多张复合键桶表，按唯一记录ID去重并精确核验，显式报告遍历预算与概率召回的边界。。完成后应交付六份可以核对的记录：规范字节、概率及保证范围、精确有限枚举、桶/ID扫描轨迹、预算漏检见证、输入拒绝与费用账单。仅写“LSH适合近邻”不算完成。

下载自包含 Python 参考和完整参考输出，在同一目录执行：

python -B algorithms-angular-lsh-check.py > ordinary.json
python -O -B algorithms-angular-lsh-check.py > optimized.json
cmp ordinary.json optimized.json
cmp ordinary.json algorithms-angular-lsh-results.json

两种运行必须逐字节一致。公开检查应报告 PASS：26,928 次符号核对、1,584 份规范编码往返、49 对集合的精确放大率、15,925 次索引/预算查询和 23 类拒绝。随机种子只用于生成有限整数测试输入，不用于冒充连续 Gaussian 定理。所有验收检查显式执行，即使 Python 禁用 assert 也不会消失。

任务一：从五个点积走到一个字节 ​

固定配置

顺序不能改变。为 $A=(2,1)$、$B=(1,2)$、$-A$ 与 $T=(1,1)$ 写出五个点积、五个有效位及低端补零后的完整字节。

核对表应包含：

再给出 f0 XOR e8 = 18（十六进制）、失配数 $2$、归一化角度估计 $2/5$。写出 $A$ 与 $B$ 的真实余弦 $4/5$，说明手选的五张平面没有给这次误差附上随机成功证书。

必须单独处理 T 的零点积：T 与 $-T$ 的第四位都为一。正倍数保持全部符号；负倍数只在点积非零处翻转。把末字节改成 f1 应因非零填充拒绝，而不是把多出的低位算进距离。

任务二：给概率保证标出量词 ​

假设使用 $q$ 张独立、各向同性连续平面，比较在抽样前固定的两个非零向量。令 $a=\theta /\pi$，交付失配数的分布、估计均值和方差：

然后推导固定 $m$ 对的同时误差界 $2m\exp (-2q{\epsilon }^2)$。若预先固定十个方向、要保证全部 $45$ 对在 $\epsilon =0.1$ 内，失败概率至多 $0.01$，取整后需要 $q=456$。这时每个载荷是 $57$ 字节；十个载荷合计 $570$ 字节，另有共享的 $456d$ 个法向量系数和配置句柄，不能只报570字节为全部存储。

交付两个保证边界的反例：

1. $q=1,\theta =\pi /3$ 时，余弦插件估计的期望是 $1/3$，真实余弦是 $1/2$；角度估计无偏不推出余弦估计无偏。
2. 看见 $G=((1,0,0),(0,1,0))$ 后选择 $(0,0,1)$ 及其相反向量，两者都是 11，真实角度却为 $\pi$。解释一般 $q<d$ 时共同零空间为何允许同样构造，并指出这是自适应选择，不能当作抽样前固定一对。

最后复核一个真正可枚举的有限实验：从四个对角法向量 $(1,1),(-1,1),(-1,-1),(1,-1)$ 独立选五次，对 $(1,0),(0,1)$ 编码。全部 $4^5=1024$ 种配置的失配数 $0,1,\dots ,5$ 计数应为

这证明该特殊对象对的二项组合计数，不能证明这四方向分布对所有夹角各向同性。

任务三：枚举独立放大，也枚举错误复用 ​

取全集 $\{0,1,2\}$ 上的六种排列，以及集合 $X=\{0,1\},Y=\{1,2\}$。按旧 MinHash 合同理路MinHash集合指纹MinHash · Min-wise hashing用所有集合共享的随机排列挑出最小键，以碰撞概率估计集合Jaccard相似度，并区分独立副本、重复键与哈希族偏差。，同一分量中 X 与 Y 必须共用排列。列出六种排列中的两个碰撞者 (1,0,2)、(1,2,0)，得到基础概率 $p=1/3$。

将四次独立抽样分别用作 $h_{0,0},h_{0,1},h_{1,0},h_{1,1}$。逐一枚举全部 $6^4=1296$ 种配置，记录至少有一张完整键相同的次数。交付

再完成两个故意修改的试验，并解释为何不能继续套这个等式：

• 同一表两分量重复同一个基础函数，单表概率成为 $1/3$；在四份原抽样的枚举空间中，对应计数为 $432$。
• 两张表重复同一对基础函数，总命中概率成为 $1/9$，对应计数为 $144$。

独立抽样中两份排列恰好相同是允许的，不能把这些配置从样本空间删去；“有放回独立抽样”与“强行共享同一个随机变量”是两件事。参考输出还核对全集全部七个非空子集的 $7^2=49$ 个有序对象对，而非只核对这一对。

任务四：把桶里的六次出现变成四次核验 ​

改用四张整数平面 $((1,0),(0,1),(1,1),(1,-1))$，$k=2,L=2$。依次插入

查询 $z=(3,1)$，精确接受条件为余弦至少 $4/5$。交付每条记录的两个键，以及完整的两张表。应有

• 表0：11 → [F,A,A2]，10 → [B]，01 → [C]；
• 表1：10 → [F]，11 → [A,A2,B]，00 → [C]；
• 查询键：表0为 11，表1为 11。

按表号与桶内顺序写出六行扫描日志：

最终首次核验列表为 [F,A,A2,B]，输出为 [A,A2]，状态为 buckets_exhausted。证明“ID唯一”如何保证去重安全，并说明 A/A2 虽方向相同也不能合并。

不得用浮点余弦的近似小数充当精确证书。对点积 $s$ 和两个平方范数 $u,v$，先判断 $s\ge 0$，再判断 $25s^2\ge 16uv$。给出 A 的 $s=7,u=5,v=10$ 与 F 的 $s=11,u=65,v=10$ 两份整数不等式；解释漏掉符号检查会怎样错误接纳反向量。

任务五：预算状态不能省略 ​

对任务四同一索引、查询和阈值，分别用预算 $0,1,2,3,4,6$ 执行查询。预算消耗的是出现项，第四项重复的 A 也花一次。应交付下表：

预算3已经找到了这组数据的全部真近点，但接口没有凭空知道这一点，仍须诚实报告还有桶项未读。预算1给出明确漏检见证；将 A 放到输入顺序最前面又会改变预算1的结果。空数据库的预算0应返回 buckets_exhausted，不能把“用完预算”与“仍有未读项”混为一谈。

推导完整候选下的近记录遗漏项 $(1-p^k{)}^L$，再把额外截断事件 $R>B$ 加入。解释为什么仅有 $\mathbb{E}[R_F]\le nL{p}_2^k$ 不足以控制总出现数 R：灰区和真近记录不在 F 内。最后指出，即使完整桶遍历后结果为空，它仍不能证明数据库没有近点。

任务六：拒绝输入、计费，再提交结果 ​

运行并保存完整 refusal_witnesses。至少手工复现以下各层拒绝，而不是只检查报错数量：

• 方向层：零向量 (0,0)、维数三的输入交给二维配置、浮点或布尔坐标、空配置、零法向量、长短不一的法向量；
• 载荷层：五位配置配空载荷、两字节 f000、非零填充 f1、可变字节数组，以及对不同配置句柄生成的两个指纹做比较；
• 索引层：$k=0$、五个基础函数却要求每表两项、重复ID或空ID、负预算或布尔预算；
• 参数层：阈值 $6/5$、分母零、排列 (0,0,2)、空集合、集合含全集外元素3。

每个拒绝必须发生在返回可信结果之前。两个不同ID带相同值则是合法输入，不应被误拒绝；阈值恰好相等应接纳。集合输入内重复元素按集合语义折叠，与记录ID冲突不是同一件事。

为任务四实表记账：共享四张二维平面有8个整数系数，原始记录有10个坐标；两张表共10个ID引用、6个非空元组键，每键2个分量，共12个键分量。完整查询读取6次出现、精确核验4个ID，输出2个ID。若另存打包指纹，那是额外存储，当前索引不靠保留这些载荷回答查询。

再给出一般式：函数参数 $Lk{S}_h$、记录存储 $S_P$、出现引用 $nL$、最坏 $nLk$ 个键分量；查询支付 $Lk$ 次基础求值、$R^{\prime }$ 次出现读取和 $V$ 次原值核验。查询空间另计规范查询副本 $S_z$ 与单次核验的最大临时空间 $W_{\mathrm{v}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{f}\mathrm{y}}$，不能漏掉整数向量的校验副本或集合交并集。说明字典期望探测、长度为k的键散列和任意精度整数位成本分别位于哪里。预算0仍然要计算查询键，不是零工作。

提交六份记录和 normal/-O 的完整一致输出。本终点的成功标准是能区分“位串语法正确、角度估计条件成立、候选命中、精确核验通过、桶已读完”这五件事，并能给每一步提供具体证据。