Relevant bibliographies by topics / Search for the nearest neighbour

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Search for the nearest neighbour'

Author: Grafiati
Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Search for the nearest neighbour.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Search for the nearest neighbour"

1

Myasnikov, E. "Exact Nearest Neighbour Search within Constrained Neighbourhood Using the Forest of Vp-Tree-Like Structures." Journal of Physics: Conference Series 2096, no. 1 (November 1, 2021): 012199. http://dx.doi.org/10.1088/1742-6596/2096/1/012199.

Full text
Abstract:
Abstract In this paper, we address the problem of fast nearest neighbour search. Unfortunately, well-known indexing data structures, such as vp-trees perform poorly on some datasets and do not provide significant acceleration compared to the brute force approach. In the paper, we consider an alternative solution, which can be applied if we are not interested in some fraction of distant nearest neighbours. This solution is based on building the forest of vp-tree-like structures and guarantees the exact nearest neighbour search in the epsilon-neighbourhood of the query point.
APA, Harvard, Vancouver, ISO, and other styles
2

N, MINOJINI, GAYATHRI R. KRISHNA, REKHA A, and SOWMIYAA P. "Dynamic Nearest Neighbour Search With Keywords." IJARCCE 4, no. 3 (March 30, 2015): 580–82. http://dx.doi.org/10.17148/ijarcce.2015.43139.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Suhaibaha, A., A. A. Rahman, U. Uznir, F. Anton, and D. Mioc. "IMPROVING NEAREST NEIGHBOUR SEARCH IN 3D SPATIAL ACCESS METHOD." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLII-2/W1 (October 26, 2016): 69–73. http://dx.doi.org/10.5194/isprs-archives-xlii-2-w1-69-2016.

Full text
Abstract:
Nearest Neighbour (NN) is one of the important queries and analyses for spatial application. In normal practice, spatial access method structure is used during the Nearest Neighbour query execution to retrieve information from the database. However, most of the spatial access method structures are still facing with unresolved issues such as overlapping among nodes and repetitive data entry. This situation will perform an excessive Input/Output (IO) operation which is inefficient for data retrieval. The situation will become more crucial while dealing with 3D data. The size of 3D data is usually large due to its detail geometry and other attached information. In this research, a clustered 3D hierarchical structure is introduced as a 3D spatial access method structure. The structure is expected to improve the retrieval of Nearest Neighbour information for 3D objects. Several tests are performed in answering Single Nearest Neighbour search and k Nearest Neighbour (kNN) search. The tests indicate that clustered hierarchical structure is efficient in handling Nearest Neighbour query compared to its competitor. From the results, clustered hierarchical structure reduced the repetitive data entry and the accessed page. The proposed structure also produced minimal Input/Output operation. The query response time is also outperformed compared to the other competitor. For future outlook of this research several possible applications are discussed and summarized.
APA, Harvard, Vancouver, ISO, and other styles
4

Hooda, Meenakshi, and Sumeet Gill. "Nearest Neighbour Search in k-dSLst Tree." Advances in Science, Technology and Engineering Systems Journal 5, no. 4 (July 2020): 160–66. http://dx.doi.org/10.25046/aj050419.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Biswas, Sumana, Sreenatha G. Anavatti, and Matthew A. Garratt. "A Time-Efficient Co-Operative Path Planning Model Combined with Task Assignment for Multi-Agent Systems." Robotics 8, no. 2 (April 26, 2019): 35. http://dx.doi.org/10.3390/robotics8020035.

Full text
Abstract:
Dealing with uncertainties along with high-efficiency planning for task assignment problem is still challenging, especially for multi-agent systems. In this paper, two frameworks—Compromise View model and the Nearest-Neighbour Search model—are analyzed and compared for co-operative path planning combined with task assignment of a multi-agent system in dynamic environments. Both frameworks are capable of dynamically controlling a number of autonomous agents to accomplish multiple tasks at different locations. Furthermore, these two models are capable of dealing with dynamically changing environments. In both approaches, the Particle Swarm Optimization-based method is applied for path planning. The path planning approach combined with the obstacle avoidance strategy is integrated with the task assignment problem. In one framework, the Compromise View model is used for completing the tasks and a combination of clustering method with the Nearest-Neighbour Search model is used to assign tasks to the other framework. The frameworks are compared in terms of computational time and the resulting path length. Results indicate that the Nearest-Neighbour Search model is much faster than the Compromise View model. However, the Nearest-Neighbour Search model generates longer paths to accomplish the mission. By following the Nearest-Neighbour Search approach, agents can successfully accomplish their mission, even under uncertainties such as malfunction of individual agents. The Nearest-Neighbour Search framework is highly effective due to its reactive structure. As per requirements, to save time, after completing its own tasks, one agent can complete the remaining tasks of other agents. The simulation results show that the Nearest-Neighbour Search model is an effective and robust way of solving co-operative path planning combined with task assignment problems.
APA, Harvard, Vancouver, ISO, and other styles
6

Zhao, Ning, Jingyue Xu, and Gang Zhou. "Fault Diagnosis of Centrifugal Fan Based on Grid Search Optimized Voting Weighted KNN." Journal of Physics: Conference Series 2636, no. 1 (November 1, 2023): 012046. http://dx.doi.org/10.1088/1742-6596/2636/1/012046.

Full text
Abstract:
Abstract Fan plays the roles of the forced draft fan, induced draft fan, primary air fan, seal fan, and powder exhauster. As an important auxiliary of the fossil-fuel power station, its working environment is harsh. Timely and efficient fault diagnosis can effectively reduce equipment failure and shutdown losses, and improve the efficiency of thermal power generation. K-Nearest Neighbour (KNN) has good classification ability for non-stationary data samples. In response to the shortcomings of the traditional KNN algorithm, this paper constructs a fault diagnosis model based on the voting weighted k-nearest neighbor algorithm. The model constructs a weight voting equation that is negatively correlated with the distance value based on the first k-nearest neighbors and then conducts fault diagnosis based on the voting score. We use grid search to optimize the model and select the k value in the model, and the relationship between the k value and accuracy was verified. The grid search optimization voting weighted k-nearest neighbor is used to diagnose the faults of nine common operating states of centrifugal fans, and the diagnostic accuracy can reach 100%.
APA, Harvard, Vancouver, ISO, and other styles
7

Suhaibah, A., U. Uznir, F. Anton, D. Mioc, and A. A. Rahman. "3D NEAREST NEIGHBOUR SEARCH USING A CLUSTERED HIERARCHICAL TREE STRUCTURE." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLI-B2 (June 7, 2016): 87–93. http://dx.doi.org/10.5194/isprs-archives-xli-b2-87-2016.

Full text
Abstract:
Locating and analysing the location of new stores or outlets is one of the common issues facing retailers and franchisers. This is due to assure that new opening stores are at their strategic location to attract the highest possible number of customers. Spatial information is used to manage, maintain and analyse these store locations. However, since the business of franchising and chain stores in urban areas runs within high rise multi-level buildings, a three-dimensional (3D) method is prominently required in order to locate and identify the surrounding information such as at which level of the franchise unit will be located or is the franchise unit located is at the best level for visibility purposes. One of the common used analyses used for retrieving the surrounding information is Nearest Neighbour (NN) analysis. It uses a point location and identifies the surrounding neighbours. However, with the immense number of urban datasets, the retrieval and analysis of nearest neighbour information and their efficiency will become more complex and crucial. In this paper, we present a technique to retrieve nearest neighbour information in 3D space using a clustered hierarchical tree structure. Based on our findings, the proposed approach substantially showed an improvement of response time analysis compared to existing approaches of spatial access methods in databases. The query performance was tested using a dataset consisting of 500,000 point locations building and franchising unit. The results are presented in this paper. Another advantage of this structure is that it also offers a minimal overlap and coverage among nodes which can reduce repetitive data entry.
APA, Harvard, Vancouver, ISO, and other styles
8

Suhaibah, A., U. Uznir, F. Anton, D. Mioc, and A. A. Rahman. "3D NEAREST NEIGHBOUR SEARCH USING A CLUSTERED HIERARCHICAL TREE STRUCTURE." ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XLI-B2 (June 7, 2016): 87–93. http://dx.doi.org/10.5194/isprsarchives-xli-b2-87-2016.

Full text
Abstract:
Locating and analysing the location of new stores or outlets is one of the common issues facing retailers and franchisers. This is due to assure that new opening stores are at their strategic location to attract the highest possible number of customers. Spatial information is used to manage, maintain and analyse these store locations. However, since the business of franchising and chain stores in urban areas runs within high rise multi-level buildings, a three-dimensional (3D) method is prominently required in order to locate and identify the surrounding information such as at which level of the franchise unit will be located or is the franchise unit located is at the best level for visibility purposes. One of the common used analyses used for retrieving the surrounding information is Nearest Neighbour (NN) analysis. It uses a point location and identifies the surrounding neighbours. However, with the immense number of urban datasets, the retrieval and analysis of nearest neighbour information and their efficiency will become more complex and crucial. In this paper, we present a technique to retrieve nearest neighbour information in 3D space using a clustered hierarchical tree structure. Based on our findings, the proposed approach substantially showed an improvement of response time analysis compared to existing approaches of spatial access methods in databases. The query performance was tested using a dataset consisting of 500,000 point locations building and franchising unit. The results are presented in this paper. Another advantage of this structure is that it also offers a minimal overlap and coverage among nodes which can reduce repetitive data entry.
APA, Harvard, Vancouver, ISO, and other styles
9

Cheung, King Lum, and Ada Wai-Chee Fu. "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD Record 27, no. 3 (September 1998): 16–21. http://dx.doi.org/10.1145/290593.290596.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ali, Mohammed Eunus, Saif-ul-Islam Khan, Sharowar Md Shahriar Khan, and Md Nasim. "Spatio-temporal keyword search for nearest neighbour queries." Journal of Location Based Services 9, no. 2 (April 3, 2015): 113–37. http://dx.doi.org/10.1080/17489725.2015.1066887.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Search for the nearest neighbour"

1

Kibriya, Ashraf Masood. "Fast Algorithms for Nearest Neighbour Search." The University of Waikato, 2007. http://hdl.handle.net/10289/2463.

Full text
Abstract:
The nearest neighbour problem is of practical significance in a number of fields. Often we are interested in finding an object near to a given query object. The problem is old, and a large number of solutions have been proposed for it in the literature. However, it remains the case that even the most popular of the techniques proposed for its solution have not been compared against each other. Also, many techniques, including the old and popular ones, can be implemented in a number of ways, and often the different implementations of a technique have not been thoroughly compared either. This research presents a detailed investigation of different implementations of two popular nearest neighbour search data structures, KDTrees and Metric Trees, and compares the different implementations of each of the two structures against each other. The best implementations of these structures are then compared against each other and against two other techniques, Annulus Method and Cover Trees. Annulus Method is an old technique that was rediscovered during the research for this thesis. Cover Trees are one of the most novel and promising data structures for nearest neighbour search that have been proposed in the literature.
APA, Harvard, Vancouver, ISO, and other styles
2

Shehu, Usman Gulumbe. "Cube technique for Nearest Neighbour(s) search." Thesis, University of Strathclyde, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.248365.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Casselryd, Oskar, and Filip Jansson. "Troll detection with sentiment analysis and nearest neighbour search." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-209474.

Full text
Abstract:
Internet trolls are gaining more influence in society due to the rapidgrowth of social media. A troll farm is a group of Internet trolls that get paid to spread certain opinions or information online. Identifying a troll farm can be difficult, since the trolls try to stay hidden. This study examines if it is possible to identify troll farms on Twitter by conducting a sentiment analysis on user tweets and modeling it as a nearest neighbor problem. The experiment was done with 4 simulated trolls and 150 normal twitter users. The users were modelled into datapoints based on the sentiment, frequency and time of their tweets. The result of the nearest neighbor search could not show a clear link between the trolls as their behaviour was not similar enough.
Internet-troll har de senaste åren fått ökat inflytande i och med ökat användande av sociala medier. En trollfarm är en grupp troll som får betalt för att sprida specifika åsikter eller information online. Det kan vara svårt att urskilja användarna i en trollfarm från vanliga användare då de ständigt försöker undvika upptäckt. I denna studie undersöks hurvida man kan finna en trollfarm  på Twitter genom att utföra en sentimentanalys på användares tweets och sedan modelera det som ett nearest neighbor problem. Experimentet utfördes med 4 simulerade troll och 150 vanliga twitteranvändare. Användarna modelerades efter tid, frekvens och sentiment på deras tweets. Resultatet från modeleringen kunde inte påvisa ett samband mellan trollen då deras beteendemönster skiljde sig åt allt för mycket.
APA, Harvard, Vancouver, ISO, and other styles
4

KUMAR, SUSMIT. "NEAREST NEIGHBOR SEARCH IN DISTRIBUTED DATABASES." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1022879916.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Ram, Parikshit. "New paradigms for approximate nearest-neighbor search." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/49112.

Full text
Abstract:
Nearest-neighbor search is a very natural and universal problem in computer science. Often times, the problem size necessitates approximation. In this thesis, I present new paradigms for nearest-neighbor search (along with new algorithms and theory in these paradigms) that make nearest-neighbor search more usable and accurate. First, I consider a new notion of search error, the rank error, for an approximate neighbor candidate. Rank error corresponds to the number of possible candidates which are better than the approximate neighbor candidate. I motivate this notion of error and present new efficient algorithms that return approximate neighbors with rank error no more than a user specified amount. Then I focus on approximate search in a scenario where the user does not specify the tolerable search error (error constraint); instead the user specifies the amount of time available for search (time constraint). After differentiating between these two scenarios, I present some simple algorithms for time constrained search with provable performance guarantees. I use this theory to motivate a new space-partitioning data structure, the max-margin tree, for improved search performance in the time constrained setting. Finally, I consider the scenario where we do not require our objects to have an explicit fixed-length representation (vector data). This allows us to search with a large class of objects which include images, documents, graphs, strings, time series and natural language. For nearest-neighbor search in this general setting, I present a provably fast novel exact search algorithm. I also discuss the empirical performance of all the presented algorithms on real data.
APA, Harvard, Vancouver, ISO, and other styles
6

Chanzy, Philippe. "Range search and nearest neighbor search in k-d trees." Thesis, McGill University, 1993. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=68164.

Full text
Abstract:
This thesis presents an analysis of the expected complexity of range searching and nearest neighbor searching in random 2-d trees. We show that range searching in a random rectangle $ Delta sb{x} times Delta sb{y}$ can be done in $O lbrack Delta sb{x} Delta sb{y} n+( Delta sb{x}+ Delta sb{y}) n sp alpha +{ rm ln} n rbrack$ expected time. A matching lower bound is also obtained. We also show that nearest neighbor searching in random 2-d trees by any algorithm must take time bounded by $ Omega lbrack n sp{ alpha-1/2}/({ rm ln} n) sp alpha rbrack$ where $ alpha=( sqrt{17}-3)/2$. This disproves a conjecture by Bentley that nearest neighbor search in random 2-d trees can be done in O(1) expected time.
APA, Harvard, Vancouver, ISO, and other styles
7

MESEJO-LEON, DANIEL ALEJANDRO. "APPROXIMATE NEAREST NEIGHBOR SEARCH FOR THE KULLBACK-LEIBLER DIVERGENCE." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2018. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=33305@1.

Full text
Abstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
PROGRAMA DE EXCELENCIA ACADEMICA
Em uma série de aplicações, os pontos de dados podem ser representados como distribuições de probabilidade. Por exemplo, os documentos podem ser representados como modelos de tópicos, as imagens podem ser representadas como histogramas e também a música pode ser representada como uma distribuição de probabilidade. Neste trabalho, abordamos o problema do Vizinho Próximo Aproximado onde os pontos são distribuições de probabilidade e a função de distância é a divergência de Kullback-Leibler (KL). Mostramos como acelerar as estruturas de dados existentes, como a Bregman Ball Tree, em teoria, colocando a divergência KL como um produto interno. No lado prático, investigamos o uso de duas técnicas de indexação muito populares: Índice Invertido e Locality Sensitive Hashing. Os experimentos realizados em 6 conjuntos de dados do mundo real mostraram que o Índice Invertido é melhor do que LSH e Bregman Ball Tree, em termos de consultas por segundo e precisão.
In a number of applications, data points can be represented as probability distributions. For instance, documents can be represented as topic models, images can be represented as histograms and also music can be represented as a probability distribution. In this work, we address the problem of the Approximate Nearest Neighbor where the points are probability distributions and the distance function is the Kullback-Leibler (KL) divergence. We show how to accelerate existing data structures such as the Bregman Ball Tree, by posing the KL divergence as an inner product embedding. On the practical side we investigated the use of two, very popular, indexing techniques: Inverted Index and Locality Sensitive Hashing. Experiments performed on 6 real world data-sets showed the Inverted Index performs better than LSH and Bregman Ball Tree, in terms of queries per second and precision.
APA, Harvard, Vancouver, ISO, and other styles
8

Varricchio, Valerio. "Efficient nearest-neighbor search algorithms for sub-Riemannian geometries." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122500.

Full text
Abstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Aeronautics and Astronautics, 2019
Cataloged from PDF version of thesis.
Includes bibliographical references.
The Motion Planning problem has been at the core of a significant amount of research in the past decades and it has recently gained traction outside academia with the rise of commercial interest in self-driving cars and autonomous aerial vehicles. Among the leading algorithms to tackle the problem are sampling-based planners, such as Probabilistic Road Maps (PRMs), Rapidly-exploring Random Trees (RRTs) and a large number of variants thereof. In this thesis, we focus on a crucial building block shared by these algorithms: nearest-neighbor search. While nearest-neighbor search is known as the asymptotically dominant bottleneck of sampling-based planners, popular algorithms to efficiently identify neighbors are limited to robots capable of unconstrained motions, commonly referred to as holonomic.
Nevertheless, this is rarely the case in the vast majority of practical applications, where the dynamical system at hand is often subject to a class of differential constraints called nonholonomic. We tackle the problem with sub-Riemannian geometries, a mathematical tool to study manifolds that can be traversed under local constraints. After drawing the parallel with nonholonomic mechanical systems, we exploit peculiar properties of these geometries and their natural notion of distance to devise specialized, efficient nearest-neighbor search algorithms. Our contributions are two-fold: First, we generalize existing space-partitioning techniques (k-d trees) to sub-Riemannian metrics. This is achieved by introducing i) a criterion - the outer Box Bound - that discards halfspaces consistently with the metric and ii) a space-partitioning technique - the Lie splitting strategy - that organizes the dataset for optimal asymptotic performance.
Second, we propose pruning techniques to further improve the query runtime. This is achieved by reducing the number of distance evaluations required to discern the nearest neighbors and exploiting heuristics that provably approximate a sub-Riemannian metric up to a constant factor, asymptotically.
by Valerio Varricchio.
Ph. D.
Ph.D. Massachusetts Institute of Technology, Department of Aeronautics and Astronautics
APA, Harvard, Vancouver, ISO, and other styles
9

Zhang, Peiwu, and 张培武. "Voronoi-based nearest neighbor search for multi-dimensional uncertain databases." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2012. http://hub.hku.hk/bib/B49618179.

Full text
Abstract:
In Voronoi-based nearest neighbor search, the Voronoi cell of every point p in a database can be used to check whether p is the closest to some query point q. We extend the notion of Voronoi cells to support uncertain objects, whose attribute values are inexact. Particularly, we propose the Possible Voronoi cell (or PV-cell). A PV-cell of a multi-dimensional uncertain object o is a region R, such that for any point p ∈ R, o may be the nearest neighbor of p. If the PV-cells of all objects in a database S are known, they can be used to identify objects that have a chance to be the nearest neighbor of q. However, there is no efficient algorithm for computing an exact PV-cell. We hence study how to derive an axis-parallel hyper-rectangle (called the Uncertain Bounding Rectangle, or UBR) that tightly contains a PV-cell. We further develop the PV-index, a structure that stores UBRs, to evaluate probabilistic nearest neighbor queries over uncertain data. An advantage of the PV-index is that upon updates on S, it can be incrementally updated. Extensive experiments on both synthetic and real datasets are carried out to validate the performance of the PV-index.
published_or_final_version
Computer Science
Master
Master of Philosophy
APA, Harvard, Vancouver, ISO, and other styles
10

Andoni, Alexandr. "Nearest neighbor search : the old, the new, and the impossible." Thesis, Massachusetts Institute of Technology, 2009. http://hdl.handle.net/1721.1/55090.

Full text
Abstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2009.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 165-178).
Over the last decade, an immense amount of data has become available. From collections of photos, to genetic data, and to network traffic statistics, modern technologies and cheap storage have made it possible to accumulate huge datasets. But how can we effectively use all this data? The ever growing sizes of the datasets make it imperative to design new algorithms capable of sifting through this data with extreme efficiency. A fundamental computational primitive for dealing with massive dataset is the Nearest Neighbor (NN) problem. In the NN problem, the goal is to preprocess a set of objects, so that later, given a query object, one can find efficiently the data object most similar to the query. This problem has a broad set of applications in data processing and analysis. For instance, it forms the basis of a widely used classification method in machine learning: to give a label for a new object, find the most similar labeled object and copy its label. Other applications include information retrieval, searching image databases, finding duplicate files and web pages, vector quantization, and many others. To represent the objects and the similarity measures, one often uses geometric notions. For example, a black-and-white image may be modeled by a high-dimensional vector, with one coordinate per pixel, whereas the similarity measure may be the standard Euclidean distance between the resulting vectors. Many other, more elaborate ways of representing objects by high-dimensional feature vectors have been studied. In this thesis, we study the NN problem, as well as other related problems that occur frequently when dealing with the massive datasets.
(cont.) Our contribution is two-fold: we significantly improve the algorithms within the classical approaches to NN, as well as propose new approaches where the classical ones fail. We focus on several key distances and similarity measures, including the Euclidean distance, string edit distance and the Earth-Mover Distance (a popular method for comparing images). We also give a number of impossibility results, pointing out the limits of the NN algorithms. The high-level structure of our thesis is summarized as follows. New algorithms via the classical approaches. We give a new algorithm for the approximate NN problem in the d-dimensional Euclidean space. For an approximation factor c > 1, our algorithm achieves dnP query time and dnl+P space for p = 1/c 2+o(1). This greatly improves on the previous algorithms that achieved p that was only slightly smaller than 1/c. The same technique also yields an algorithm with dno(p) query time and space near-linear in n. Furthermore, our algorithm is near-optimal in the class of "hashing" algorithms. Failure of the classical approaches for some hard distances. We give an evidence that the classical approaches to NN under certain hard distances, such as the string edit distance, meet a concrete barrier at a nearly logarithmic approximation. Specifically, we show that for all classical approaches to NN under the edit distance, involving embeddings into a general class of spaces (such as l1, powers of l2, etc), the resulting approximation has to be at least near-logarithmic in the strings' length. A new approach to NN under hard distances.
(cont.) Motivated by the above impossibility results, we develop a new approach to the NN problem, where the classical approaches fail. Using this approach, we give a new efficient NN algorithm for a variant of the edit distance, the Ulam distance, which achieves a double-logarithmic approximation. This is an exponential improvement over the lower bound on the approximation achievable via the previous classical approaches to this problem. Data structure lower bounds. To complement our algorithms, we prove lower bounds on NN data structures for the Euclidean distance and for the mysterious but important case of the ... distance. In both cases, our lower bounds are the first ones to hold in the same computational model as the respective upper bounds. Furthermore, for both problems, our lower bounds are optimal in the considered models. External applications. Although our main focus is on the NN problem, our techniques naturally extend to related problems. We give such applications for each of our algorithmic tools. For example, we give an algorithm for computing the edit distance between two strings of length d in near-linear time. Our algorithm achieves approximation 20 ..., improving over the previous bound of ... . We note that this problem has a classical exact algorithm based on dynamic programming, running in quadratic time.
by Alexandr Andoni.
Ph.D.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Search for the nearest neighbour"

1

Large Scale Nearest Neighbor Search - Theories, Algorithms, and Applications. [New York, N.Y.?]: [publisher not identified], 2014.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Weber, Roger. Similarity search in high dimensional vector spaces. Berlin: Aka, 2001.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Başan, Ghillie. The moon's our nearest neighbour. London: Warner Books, 2001.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Roopchansingh, Ajay. Nearest neighbour interconnect architecture in deep-submicron FPGAs. Ottawa: National Library of Canada, 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Gwennyth, Zainu'ddin Ailsa, Australian Indonesian Association Victoria, and Monash University. Centre of Southeast Asian Studies., eds. Nearest southern neighbour: Some Indonesian views of Australia and Australians. Clayton, Vic., Australia: Monash University, 1986.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Guo, Gongde. A study on the nearest neighbour method and its applications. [S.l: The Author], 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Brandsma, Theo. Rainfall generator for the Rhine Basin: Single-site generation of weather variables by nearest-neighbour resampling. De Bilt, Netherlands: KNMI, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Nearest Neighbor Search. Springer US, 2005. http://dx.doi.org/10.1007/0-387-27544-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Papadopoulos, Apostolos N., and Yannis Manolopoulos. Nearest Neighbor Search : : A Database Perspective. Springer London, Limited, 2006.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Manolopoulos, Yannis, and Apostolos N. N. Papadopoulos. Nearest Neighbor Search : : A Database Perspective. Springer, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Search for the nearest neighbour"

1

Shekhar, Shashi, and Hui Xiong. "Nearest Neighbor Search." In Encyclopedia of GIS, 783. Boston, MA: Springer US, 2008. http://dx.doi.org/10.1007/978-0-387-35973-1_867.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Khan, Omar Shahbaz, Martin Aumüller, and Björn Þór Jónsson. "Suitability of Nearest Neighbour Indexes for Multimedia Relevance Feedback." In Similarity Search and Applications, 133–47. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-46994-7_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Serrano, Aureo, Luisa Micó, and Jose Oncina. "Which Fast Nearest Neighbour Search Algorithm to Use?" In Pattern Recognition and Image Analysis, 567–74. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38628-2_67.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Weller, Frank, and Robert Mencl. "Nearest Neighbour Search for Visualization Using Arbitrary Triangulations." In Eurographics, 191–200. Vienna: Springer Vienna, 1996. http://dx.doi.org/10.1007/978-3-7091-7488-3_20.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chappell, Timothy, Shlomo Geva, and Guido Zuccon. "Approximate Nearest-Neighbour Search with Inverted Signature Slice Lists." In Lecture Notes in Computer Science, 147–58. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-16354-3_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Gómez-Ballester, Eva, Luisa Micó, and Jose Oncina. "Some Improvements in Tree Based Nearest Neighbour Search Algorithms." In Lecture Notes in Computer Science, 456–63. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-24586-5_56.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Shaneck, Mark, Yongdae Kim, and Vipin Kumar. "Privacy Preserving Nearest Neighbor Search." In Machine Learning in Cyber Trust, 247–76. Boston, MA: Springer US, 2009. http://dx.doi.org/10.1007/978-0-387-88735-7_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Hruz, Tomas, and Marcel Schöngens. "Partially Specified Nearest Neighbor Search." In Lecture Notes in Computer Science, 372–83. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32241-9_32.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Komorowski, Michał, and Tomasz Trzciński. "Random Binary Search Trees for Approximate Nearest Neighbour Search in Binary Space." In Lecture Notes in Computer Science, 473–79. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-69900-4_60.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Wu, Xing, Geoffrey Holmes, and Bernhard Pfahringer. "Mining Arbitrarily Large Datasets Using Heuristic k-Nearest Neighbour Search." In AI 2008: Advances in Artificial Intelligence, 355–61. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-89378-3_35.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Search for the nearest neighbour"

1

Ferro, Demetrio, Vincent Gripon, and Xiaoran Jiang. "Nearest Neighbour Search using binary neural networks." In 2016 International Joint Conference on Neural Networks (IJCNN). IEEE, 2016. http://dx.doi.org/10.1109/ijcnn.2016.7727873.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Dick, Travis, Camilo Perez, Martin Jagersand, and Azad Shademan. "Realtime Registration-Based Tracking via Approximate Nearest Neighbour Search." In Robotics: Science and Systems 2013. Robotics: Science and Systems Foundation, 2013. http://dx.doi.org/10.15607/rss.2013.ix.044.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Stommel, Martin, Stefan Edelkamp, Thiemo Wiedemeyer, and Michael Beetz. "Fractal Approximate Nearest Neighbour Search in Log-Log Time." In British Machine Vision Conference 2013. British Machine Vision Association, 2013. http://dx.doi.org/10.5244/c.27.18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Vijay, Savinu T., and P. N. Pournami. "Feature Based Image Registration using Heuristic Nearest Neighbour Search." In 2018 22nd International Computer Science and Engineering Conference (ICSEC). IEEE, 2018. http://dx.doi.org/10.1109/icsec.2018.8712669.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Kurniawati, R., J. S. Jin, and J. A. Shepherd. "An efficient nearest-neighbour search while varying Euclidean metrics." In the sixth ACM international conference. New York, New York, USA: ACM Press, 1998. http://dx.doi.org/10.1145/290747.290812.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Shao, Zhou, and David Taniar. "Range-based Nearest Neighbour Search in a Mobile Environment." In MoMM '14: The 12th International Conference on Advances in Mobile Computing and Multimedia. New York, NY, USA: ACM, 2014. http://dx.doi.org/10.1145/2684103.2684158.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Chatterjee, Bapi, Ivan Walulya, and Philippas Tsigas. "Concurrent Linearizable Nearest Neighbour Search in LockFree-kD-tree." In ICDCN '18: 19th International Conference on Distributed Computing and Networking. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3154273.3154307.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Moreno-Seco, F., L. Mico, and J. Oncina. "A new classification rule based on nearest neighbour search." In Proceedings of the 17th International Conference on Pattern Recognition, 2004. ICPR 2004. IEEE, 2004. http://dx.doi.org/10.1109/icpr.2004.1333789.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Tellez, Eric Sadit, Edgar Chávez, and Gonzalo Navarro. "Succinct nearest neighbor search." In the Fourth International Conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/1995412.1995420.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

"Grid-based Spatial Index Method for Location-based Nearest Neighbour Search." In 2019 the 9th International Workshop on Computer Science and Engineering. WCSE, 2019. http://dx.doi.org/10.18178/wcse.2019.03.030.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Search for the nearest neighbour"

1

Gonzales, Antonio, and Nicholas Paul Blazier. Enhanced Approximate Nearest Neighbor via Local Area Focused Search. Office of Scientific and Technical Information (OSTI), February 2017. http://dx.doi.org/10.2172/1367491.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Mackey, Greg Edward. Efficient nearest neighbor searches in N-ABLE. Office of Scientific and Technical Information (OSTI), July 2010. http://dx.doi.org/10.2172/992313.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Search for the nearest neighbour' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography