СТРУКТУРА СО СВОЙСТВАМИ ТЕСНОГО МИРА ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА БЛИЖАЙШЕГО СОСЕДА В МЕТРИЧЕСКОМ ПРОСТРАНСТВЕ |
| 5 | |
| 2012 |
| научная статья | 004.057.4 | ||
| 409-415 | поиск в метрическом пространстве, структура данных, тесный мир, вероятностный поиск, распределенные системы |
| Рассматривается новый подход к решению задачи поиска ближайшего соседа в метрическом пространстве. Предлагается в качестве структуры данных использовать граф, обладающий навигационными свойствами тесного мира, а в качестве алгоритма поиска – алгоритм градиентного спуска. Проблема существования локальных минимумов решается за счет произведения серии независимых поисков. Приведены экспериментальные данные, подтверждающие логарифмическую сложность алгоритма поиска. |
 |
| 1 . Cover T.M., Hart P.E. Nearest neighbor pattern classification // Information Theory IEEE Transactions on. Jan. 1967. Vol. 13, No 1. P. 21–27. 2 . Flickner M., et al. Query by image and video content: the QBIC system // Computer. Sep. 1995. Vol. 28, No 9. P. 23–32. 3 . Salzberg S., Cost S. A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features // Machine Learning. 1993. Vol. 10, No 1. P. 57–78. 4 . Sarwar B., Karypis G., Konstan J., Reidl J. Item-based collaborative filtering recommendation algorithms // Proceedings of the 10th International Conference on World Wide Web. New York, USA, 2001. P. 285–295. 5 . Rhoads R.E., Rychli W., Unknown R. A computer program for choosing optimal oligonudeotides for filter hybridization, sequencing and in vitro amplification of DNA // Nucletic Acids Research. Oct. 1989. Vol. 17, No 21. P. 8543–8551. 6 . Deerwester S., Dumais S., Furnas G. et al. Indexing by Latent Semantic Analysis // J. Amer. Soc. Inform. Sci. 1990. Vol. 41. P. 391–407. 7 . Ch?vez E., Navarro G., Baeza-Yates R., Marroqu?n J.L. Searching in metric space // Journal ACM Computing Surveys (CSUR). Sep. 2001. Vol. 33, No 3. P. 273–321. 8 . Kleinberg J. The Small-World Phenomenon: An Algorithmic Perspective // Annual ACM Symposium on Theory of Computing. 2000. Vol. 32. P. 163–170. 9 . Aurenhammer F. Voronoi diagrams – a survey of a fundamental geometric data structure // ACM Computing Surveys (CSUR). Sep. 1991. Vol. 23, No 3. P. 345–405. 10 . Beaumont O., Kermarrec A.-M., Marchal L., Riviere E. VoroNet: A scalable object network based on Voronoi tessellations // International Parallel and Distributed Processing Symposium. Long Beach, USA, 2007. P. 20. 11 . Navarro G. Searching in metric spaces by spatial approximation // String Processing and Informa- tion Retrieval Symposium. Cancun, Mexico, 1999. P. 141–148. 12 . Bentley J.L. Multidimensional binary search trees used for associative searching // Communications of the ACM. Sep. 1975. Vol. 18, No 9. P. 509–517. 13 . Bentley J.L., Finkel R. Quad Trees: A Data Structure for Retrieval on Composite Keys // Acta Informatica. 1974. Vol. 4, No 1. P. 1–9. 14 . Wong, Lee Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees // Acta Informatica. 1977. Vol. 9, No 1. P. 23–29. 15 . Samet H. The design and analysis of spatial data structures. Reading, MA: Addison-Wesley, 1989. 16 . Mount D.M., Arya S., Narayan O. Accounting for boundary effects in nearest-neighbor searching // Discrete & Computational Geometry. 1996. Vol. 16, No 2. P. 155–176. 17 . Dobkin D., Lipton R. Multidimensional Searching Problems // SIAM J. Comput. 1976. Vol. 5, No 2. P. 181–186. 18 . Bozkaya T., Ozsoyoglu M. Distance-based indexing for high-dimensional metric spaces // Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. New York, USA, 1997. P. 357–368. 19 . Yianilos P. Data structures and algorithms for nearest neighbor search in general metric spaces // SODA'93 Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, USA, 1993. P. 311–321. 20 . Arya S., Mount D. Approximate nearest neighbor queries in fixed dimensions // SODA'93 Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA, USA, 1993. P. 271–280. 21 . Kleinberg J. Two algorithms for nearest-neighbor search in high dimensions // STOC'97 Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. New York, USA, 1997. P. 599–608. 22 . Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality // STOC '98 Proceedings of the Thirtieth Annual ACM Sym-posium on Theory of Computing. New York, USA, 1998. P. 604–613. 23 . Kushilevitz E., Ostrovsky R., Rabani Y. Efficient search for approximate nearest neighbor in high dimensional spaces // STOC'98 Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. New York, NY, USA, 1998. P. 614–623. 24 . Gionis A., Indyk P., Motwani R. Similarity Search in High Dimensions via Hashing // VLDB'99 Proceedings of the 25th International Conference on Very Large Data Bases. San Francisco, USA, 1999. P. 518–529. 25 . Datar M., Immorlica N., Indyk P., Mirro- kni V. Locality-sensitive hashing scheme based on p-stable distributions // SCG'04 Proceedings of the Twentieth Annual Symposium on Computational Geometry. New York, USA, 2004. P. 253–262. 26 . Andoni A., Indyk P. Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions // 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). Berkeley, California, 2006. P. 459–468. 27 . Beaumont O., Kermarrec A.-M., Rivi?re ?. Peer to peer multidimensional overlays: approximating complex structures // Proceedings of the 11th International Conference on Principles of Distributed Systems. Berlin, Heidelberg, 2007. P. 315–328. 28 . Krylov V.V., Logvinov A.A., Ponomarenko A.A., Ponomarev D.M. Metrized Small World Properties Data Structure // SEDE. Los Angeles, California, USA, 2008 |