可以在动态数据上使用局部敏感哈希

Question

局部敏感散列可以用于动态数据吗?例如，假设我首先对1,000,000个文档使用LSH，并将结果存储在索引中，然后我想将另一个文档添加到创建的索引中。我可以使用LSH吗?

Answer 1

是。

由于lsh使用多个哈希来生成多个签名，那么这些签名将被绑定来生成索引。如果存储随机散列函数和分组过程，则可以重用它来为新插入生成索引。因此，对于每个新的插入，您将有相应的索引

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