局部敏感哈希能在动态数据上使用吗？

Question

局部敏感哈希算法是否可用于动态数据？例如，假设我首先将LSH应用于1000000个文档并将结果存储在索引中，然后我想将另一个文档添加到创建的索引中。我能用LSH来完成吗？

- Janitha Tennakoon

Answer 1

可以的。

由于lsh使用多个哈希函数生成多个签名，然后将这些签名绑定以生成索引。如果您存储了随机哈希函数和绑定过程，则可以重复使用它们来为新插入生成索引。因此，每个新插入都会有相应的索引。

- Averman

Answer 2

是的，您可以这样做。您只需要计算新增文档与其他文档之间的Jaccard相似度，并将其添加到索引中即可。

TABLE Documents (
  ID INT IDENTITY(1,1) PRIMARY KEY NOT NULL, 
  MinHashes BINARY(512), -- serialized Min Hash results
  Name NVARCHAR(255) UNIQUE NOT NULL, 
  Content VARBINARY(MAX)
)

TABLE SimilarDocumentIndex (
  DocumentAID INT REFERENCES Documents(ID),
  DocumentBID INT REFERENCES Documents(ID),
  Similarity FLOAT, -- Jaccard Similarity 0.0...1.0
  PRIMARY KEY CLUSTERED (DocumentAID, DocumentBID)
)

--
-- Find similar documents
--
SELECT TOP 20 DISTINCT DocumentID
FROM (SELECT 
FROM SimilarDocumentIndex 
WHERE DocumentAID = @DocumentID 
ORDER BY Similarity DESC

--
-- Compare two documents
--    
SELECT Similarity 
FROM SimilarDocumentIndex 
WHERE DocumentAID = @DocumentAID AND DocumentBID = @DocumentBID

--
-- Adding a new document
--
SET @MinHashes = dbo.CalcMinHashes(@content)

INSERT INTO Document 
VALUES(@MinHashes, @name, @content)

SET @DocumentID = SCOPE_IDENTITY()

INSERT INTO SimilarDocumentIndex
  SELECT @DocumentID, ID, dbo.JaccardSimilarity(@MinHashes, MinHashes)
  FROM Documents 
  WHERE ID <> @DocumentID 

INSERT INTO SimilarDocumentIndex
  SELECT DocumentBID, @DocumentID, Similarity
  FROM SimilarDocumentIndex
  WHERE DocumentAID = @DocumentID

- Louis Ricci

---

抱歉，我所说的索引并不是指数据库索引，而是指哈希表数据结构。我想知道是否可以再次使用LSH算法将新文档分配到与1000个文档相同的桶中。 - Janitha Tennakoon

只要您没有设置最大桶大小，我认为它应该可以正常工作。因此，这取决于您使用的实现方式。 - Louis Ricci

计算新增文档与其他文档的Jaccard相似度已经不再是一个选项，因为现在我有数百万个文档。 - Janitha Tennakoon

@janitha000 - 计算一百万个文档的相似度并不是那么糟糕，我建议在假设它不可行之前尝试实现基准测试。也许你可以将相似度留空，并使用异步作业每小时、每分钟或每次更新它。 - Louis Ricci