[SPARK-18454] Changes to improve Nearest Neighbor Search for LSH

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Incomplete
• Component/s: ML
• Labels: bulk-closed
• Assignee: Unassigned
• Reporter: Yun Ni
• Created: 15/Nov/16 21:17
• Updated: 04/Dec/19 07:11
• Resolved: 21/May/19 04:12

Description

We all agree to do the following improvement to Multi-Probe NN Search:
(1) Use approxQuantile to get the hashDistance threshold instead of doing full sort on the whole dataset

Currently we are still discussing the following:
(1) What hashDistance (or Probing Sequence) we should use for MinHash
(2) What are the issues and how we should change the current Nearest Neighbor implementation

Issue Links

• contains: SPARK-18334 What hashDistance should MinHash use?
• contains: SPARK-18409 LSH approxNearestNeighbors should use approxQuantile instead of sort
• contains: SPARK-30120 LSH approxNearestNeighbors should use BoundedPriorityQueue when numNearestNeighbors is small
• Is contained by: SPARK-18392 LSH API, algorithm, and documentation follow-ups