Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection Article Swipe

MAKE IMPACT

Kashish Mittal , Harsh Shah , Ajit Rajwade · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2311.02573

This work presents an adaptive group testing framework for the range-based high dimensional near neighbor search problem. Our method efficiently marks each item in a database as neighbor or non-neighbor of a query point, based on a cosine distance threshold without exhaustive search. Like other methods for large scale retrieval, our approach exploits the assumption that most of the items in the database are unrelated to the query. However, it does not assume a large difference between the cosine similarity of the query vector with the least related neighbor and that with the least unrelated non-neighbor. Following a multi-stage adaptive group testing algorithm based on binary splitting, we divide the set of items to be searched into half at each step, and perform dot product tests on smaller and smaller subsets, many of which we are able to prune away. We show that, using softmax-based features, our method achieves a more than ten-fold speed-up over exhaustive search with no loss of accuracy, on a variety of large datasets. Based on empirically verified models for the distribution of cosine distances, we present a theoretical analysis of the expected number of distance computations per query and the probability that a pool will be pruned. Our method has the following features: (i) It implicitly exploits useful distributional properties of cosine distances unlike other methods; (ii) All required data structures are created purely offline; (iii) It does not impose any strong assumptions on the number of true near neighbors; (iv) It is adaptable to streaming settings where new vectors are dynamically added to the database; and (v) It does not require any parameter tuning. The high recall of our technique makes it particularly suited to plagiarism detection scenarios where it is important to report every database item that is sufficiently similar item to the query.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2311.02573

PDF

https://arxiv.org/pdf/2311.02573

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4388482439

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4388482439

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2311.02573

Digital Object Identifier

Title

Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-11-05

Full publication date if available

Authors

Kashish Mittal, Harsh Shah, Ajit Rajwade

List of authors in order

Landing page

https://arxiv.org/abs/2311.02573

Publisher landing page

PDF URL

https://arxiv.org/pdf/2311.02573

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2311.02573

Direct OA link when available

Concepts

Nearest neighbor search, Best bin first, Cosine similarity, Dot product, Computer science, Set (abstract data type), Range (aeronautics), Algorithm, Binary search algorithm, k-nearest neighbors algorithm, Binary number, Similarity (geometry), Pattern recognition (psychology), Data mining, Search algorithm, Mathematics, Image (mathematics), Artificial intelligence, Materials science, Geometry, Programming language, Arithmetic, Composite material

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload