ANN search is known to outperform NN search in terms of efficiency and some techniques reduce storage space from compact representations. But what happens in terms of effectiveness? Is it possible to achieve the same performance without finding the nearest neighbor with exhaustive search?
Can ANN search surpass the accuracy of NN search in large databases with high-dimensional representations?
125 Views Asked by jperezmartin At
2
There are 2 best solutions below
2
gsamaras
On
If by effectiveness, you mean accuracy (i.e. finding the exact nearest neighbor), then no. NN search will always find the exact NN, while ANN search will, at its best chance, find the exact NN, that is a tie at the result with NN search.
However, in a high dimensional space the curse of dimensionality lurks and the usual data structures and algorithms for 2D and 3D tend to be as slow as the brute force search, thus an ANN search is the way to go, when you (big) data live in a high dimensional space.
Related Questions in ALGORITHM
- Two different numbers in an array which their sum equals to a given value
- Given two arrays of positive numbers, re-arrange them to form a resulting array, resulting array contains the elements in the same given sequence
- Time complexity of the algorithm?
- Find a MST in O(V+E) Time in a Graph
- Why k and l for LSH used for approximate nearest neighbours?
- How to count the number of ways of choosing of k equal substrings from a List L(the list of All Substrings)
- Issues with reversing the linkedlist
- Finding first non-repeating number in integer array
- Finding average of an array
- How to check for duplicates with less time in a list over 9000 elements by python
- How to pick a number based on probability?
- Insertion Sort help in javascript -- Khan Academy
- Developing a Checkers (Draughts) engine, how to begin?
- Can Bellman-Ford algorithm be used to find shorthest path on a graph with only positive edges?
- What is the function for the KMP Failure Algorithm?
Related Questions in PERFORMANCE
- Slow performance on ipad erasing image
- Can Apache Ant be told to cache its XML files?
- What are the pros and cons of the picture element?
- DB candidate as CouchDB/Schema replacement
- python member str performance too slow
- Split a large query (2 days) into pieces to increase the speed in Postgres
- Use GUI displayed results of SQL query vs new queries?
- fastest way to map a large number of longs
- Bash regular expression execution hangs on long expressions
- Why is calling a function so slow in Javascript?
- Performance of element-compare in java collections
- "Capture GPU Frame" in XCode -- iOS only?
- Efficiency penalty of initializing a struct/class within a loop
- Change the rotating speed of the circle when the mouse moves using javascript
- Replace foreach to make loop into queryable
Related Questions in SEARCH
- SQL weight rows by formula
- If Input is focused trigger X else trigger Y
- laravel full-text search with multiple keywords together
- Login form by using a new database, made in VB
- How to search for overloaded methods in a class
- Modifying Tries code in Java
- Doing a multi-column search for an item in a listView control using c#
- T SQL wildcard searching for a zip code
- django rest framework search filter all fields
- how to filter search result with dropdown list in php
- PHP/MySQL search... show all data by default, or show matched data
- Oracle multiple REPLACE options in REGEXP_REPLACE
- Is there a way to get all complete sentences that a search engine (e.g. Google) has indexed that contain two search terms?
- How to search a unknown composite key for dictionary in O(1) in c#
- android java search listview clickedItem
Related Questions in NEAREST-NEIGHBOR
- NearestNeighbors tradeoff - run faster with less accurate results
- Algorithm to find k neighbors in a certain range?
- Python find list of surrounding neighbours of a node in 2D array
- how to get k nearest neighbors using weka kdtree
- example from LSHForest, results not convinced
- NxN array check neighbors cells
- Postgres: How to find nearest tsrange from timestamp outside of ranges?
- Any way to allow nans in python sklearn K nearest neighbors?
- Can ANN search surpass the accuracy of NN search in large databases with high-dimensional representations?
- IndexError: list index out of range in python k nearest neighbour
- Dataset for meaningless “Nearest Neighbor”?
- k-means clustering for Testing data classification
- Find closest point of labelled area to a point in an image with Matlab
- KNearest Neighbors in sklearn - ValueError: query data dimension must match training data dimension
- Input dimensions for distance function for nearest neighbors
Related Questions in APPROXIMATE-NN-SEARCHING
- Why k and l for LSH used for approximate nearest neighbours?
- Can ANN search surpass the accuracy of NN search in large databases with high-dimensional representations?
- Attempting to implement a C++ library, need some pointers on how to interface with it
- How does FLANN select what algorithm and parameters to use?
- Adding an element to a VP tree (VP tree maintenance)
- Unable to combine "bool" query with "knn" query - Elastisearch
- Searching for closest statistically significant match in k-dimensional set
- Nearest neighbor search over Levenshtein distance in Python using metric indexing
- Best data structure for high dimensional nearest neighbor search
- What modules should be included in CMakeList.txt for Approximate Nearest Neighbor Searching?
- Populating an array from a .txt file
- Performance of Annoy method Vs. KD-Tree
- How does ElasticSearch create a vector representation of a document?
- Weaviate - top hits for with_near_vector() doesn't include the record whose vector perfectly matches query vector
- Reinforcement Learning in arbitrarily large action/state spaces
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
I tried binary search and ann search on ip2location database. It has the same speed but with many optimizations. You can find a source code at https://ip2locationphp.codeplex.com/.