000129301 001__ 129301
000129301 005__ 20190316234424.0
000129301 037__ $$aCONF
000129301 245__ $$aDistributed Similarity Search in High Dimensions Using Locality Sensitive Hashing
000129301 260__ $$c2009
000129301 269__ $$a2009
000129301 336__ $$aConference Papers
000129301 520__ $$aIn this paper we consider distributed K-Nearest Neighbor (KNN) search and range query processing in high dimensional data. Our approach is based on Locality Sensitive Hashing (LSH) which has proven very efficient in answering KNN queries in centralized settings. We consider mappings from the multi-dimensional LSH bucket space to the linearly ordered set of peers that jointly maintain the indexed data and derive requirements to achieve high quality search results and limit the number of network accesses. We put forward two such mappings that come with these salient properties: being locality preserving so that buckets likely to hold similar data are stored on the same or neighboring peers and having a predictable output distribution to ensure fair load balancing. We show how to leverage the linearly aligned data for efficient KNN search and how to efficiently process range queries which is, to the best of our knowledge, not possible in existing LSH schemes. We show by comprehensive performance evaluations using real world data that our approach brings major performance and accuracy gains compared to state-of-the-art.
000129301 6531_ $$aK-nearest neighbor search
000129301 6531_ $$asimilarity search
000129301 6531_ $$aP2P
000129301 6531_ $$aLSH
000129301 6531_ $$aNCCR-MICS
000129301 6531_ $$aNCCR-MICS/CL4
000129301 700__ $$0242027$$aHaghani, Parisa$$g173051
000129301 700__ $$aMichel, Sebastian
000129301 700__ $$0240941$$aAberer, Karl$$g134136
000129301 7112_ $$a12th International Conference on Extending Database Technology (EDBT)$$cSaint-Petersburg, Russia$$dMarch 23-26 2009
000129301 773__ $$tProceedings of the 12th International Conference on Extending Database Technology (EDBT'09)
000129301 8564_ $$uhttp://www.math.spbu.ru/edbticdt/$$zURL
000129301 909C0 $$0252004$$pLSIR$$xU10405
000129301 909CO $$ooai:infoscience.tind.io:129301$$pconf$$pIC$$qGLOBAL_SET
000129301 937__ $$aLSIR-CONF-2008-058
000129301 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000129301 980__ $$aCONF