algorithm - ローカリティ センシティブ ハッシングは動的データで使用できますか?

Question

ローカリティ センシティブ ハッシングは動的データで使用できますか? たとえば、最初に 1,000,000 個のドキュメントに対して LSH を使用し、その結果をインデックスに保存するとします。次に、作成したインデックスに別のドキュメントを追加したいとします。LSHでできますか？

Answer 1

はい、できます。追加されたドキュメントと残りのドキュメントの 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